View source for LZMA

{{Short description|Lossless data compression algorithm}}
{{For|the airport with the ICAO code "LZMA"|Martin Airport (Slovakia)}}

The '''Lempel–Ziv–Markov chain algorithm'''<ref>{{cite book |last1=Salomon |first1=David |title=Data Compression: The Complete Reference |date=March 20, 2007 |publisher=Springer London |isbn=9781846286032 |page=242}}</ref> ('''LZMA''') is an [[algorithm]] used to perform [[lossless data compression]]. It has been used in the [[7z]] format of the [[7-Zip]] archiver since 2001.<ref name="7z_format">{{cite web|author1=Igor Pavlov|title=7z Format|url=http://www.7-zip.org/7z.html|date=2001-12-05|archive-url=https://web.archive.org/web/20011205060104/http://www.7-zip.org/7z.html |archive-date=5 December 2001 }}</ref> This algorithm uses a [[Dictionary coder|dictionary compression]] scheme somewhat similar to the [[LZ77]] algorithm published by [[Abraham Lempel]] and [[Jacob Ziv]] in 1977 and features a high compression ratio (generally higher than [[bzip2]])<ref name=gzip_bzip_lzma_bench>{{cite web|author1=Lasse Collin|title=A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA|url=http://tukaani.org/lzma/benchmarks.html|access-date=2015-10-21|date=2005-05-31}} - LZMA Unix Port was finally replaced by xz which features better and faster compression; from here we know even LZMA Unix Port was a lot better than gzip and bzip2.</ref><ref>{{cite web
 |url          = http://blog.i-no.de/archives/2008/05/08/index.html#e2008-05-08T16_35_13.txt
 |title        = Gzip, Bzip2 and Lzma compared
 |last         = Klausmann
 |first        = Tobias
 |date         = 2008-05-08
 |work         = Blog of an Alpha animal
 |access-date   = 2013-06-16
 |archive-url  = https://web.archive.org/web/20130106193958/http://blog.i-no.de/archives/2008/05/08/index.html#e2008-05-08T16_35_13.txt
 |archive-date = 2013-01-06
 |url-status     = dead
}}</ref> and a variable compression-dictionary size (up to 4&nbsp;[[Gigabyte|GB]]),<ref name="LZMA Format">{{cite web
| url=http://www.7-zip.org/7z.html
| title=7z Format
| year=2013
| author=Unknown
| access-date=2013-06-16}}</ref> while still maintaining decompression speed similar to other commonly used compression algorithms.<ref>
{{cite web 
| url=http://mattmahoney.net/dc/dce.html#Section_52 
|title=Data Compression Explained 
|last=Mahoney 
|first=Matt
|access-date=2013-11-13}}</ref>

'''LZMA2''' is a simple container format that can include both uncompressed data and LZMA data, possibly with multiple different LZMA encoding parameters.  LZMA2 supports arbitrarily scalable multithreaded compression and decompression and efficient compression of data which is partially incompressible.<ref name=xz-inadequate>{{cite web
 |url=http://lzip.nongnu.org/xz_inadequate.html
 |title=Xz format inadequate for long-term archiving
 |author=Antonio Diaz Diaz
 |access-date=2018-07-20}}</ref>

== Overview ==
LZMA uses a [[Dictionary coder|dictionary compression]] algorithm (a variant of [[LZ77]] with huge dictionary sizes and special support for repeatedly used match distances), whose output is then encoded with a [[range encoding|range encoder]], using a complex model to make a probability prediction of each bit.  The dictionary compressor finds matches using sophisticated dictionary data structures, and produces a stream of literal symbols and phrase references, which is encoded one bit at a time by the range encoder: many encodings are possible, and a [[dynamic programming]] algorithm is used to select an optimal one under certain approximations.<ref name=lzma-sdk-format/>

Prior to LZMA, most encoder models were purely byte-based (i.e. they coded each bit using only a cascade of contexts to represent the dependencies on previous bits from the same byte).  The main innovation of LZMA is that instead of a generic byte-based model, LZMA's model uses contexts specific to the bitfields in each representation of a literal or phrase: this is nearly as simple as a generic byte-based model, but gives much better compression because it avoids mixing unrelated bits together in the same context. Furthermore, compared to classic dictionary compression (such as the one used in [[ZIP (file format)|zip]] and [[gzip]] formats), the dictionary sizes can be and usually are much larger, taking advantage of the large amount of memory available on modern systems.<ref name=lzma-sdk-format/>

==Compressed format overview==
In LZMA compression, the compressed stream is a stream of bits, encoded using an adaptive binary range coder. The stream is divided into packets, each packet describing either a single byte, or an LZ77 sequence with its length and distance implicitly or explicitly encoded.  Each part of each packet is modeled with independent contexts, so the probability predictions for each bit are correlated with the values of that bit (and related bits from the same field) in previous packets of the same type.
Both the lzip<ref name=lzip-format>{{cite web |title=Lzip Stream Format |url=https://www.nongnu.org/lzip/manual/lzip_manual.html#Stream-format |website=Lzip Manual |access-date=14 November 2019}}</ref> and the LZMA SDK documentation describe this stream format.<ref name=lzma-sdk-format/>

There are 7 types of packets:<ref name=lzip-format/>
{{table alignment}}
{| class="wikitable col1right"
|-
! Packed code (bit sequence)
! Packet name
! Packet description
|-
| 0 + byteCode
| LIT
| A single byte encoded using an adaptive binary range coder.
|-
| 1+0 + len + dist
| MATCH
| A typical LZ77 sequence describing sequence length and distance.
|-
| 1+1+0+0
| SHORTREP
| A one-byte LZ77 sequence. Distance is equal to the last used LZ77 distance.
|-
| 1+1+0+1 + len
| LONGREP[0]
| An LZ77 sequence. Distance is equal to the last used LZ77 distance.
|-
| 1+1+1+0 + len
| LONGREP[1]
| An LZ77 sequence. Distance is equal to the second last used LZ77 distance.
|-
| 1+1+1+1+0 + len
| LONGREP[2]
| An LZ77 sequence. Distance is equal to the third last used LZ77 distance.
|-
| 1+1+1+1+1 + len
| LONGREP[3]
| An LZ77 sequence. Distance is equal to the fourth last used LZ77 distance.
|}

LONGREP[*] refers to LONGREP[0–3] packets, *REP refers to both LONGREP and SHORTREP, and *MATCH refers to both MATCH and *REP.

LONGREP[n] packets remove the distance used from the list of the most recent distances and reinsert it at the front, to avoid useless repeated entry, while MATCH just adds the distance to the front even if already present in the list and SHORTREP and LONGREP[0] don't alter the list.

The length is encoded as follows:
{| class="wikitable col1right"
|-
! Length code (bit sequence)
! Description
|-
| 0+ 3 bits
| The length encoded using 3 bits, gives the lengths range from 2 to 9.
|-
| 1+0+ 3 bits
| The length encoded using 3 bits, gives the lengths range from 10 to 17.
|-
| 1+1+ 8 bits
| The length encoded using 8 bits, gives the lengths range from 18 to 273.
|}

As in LZ77, the length is not limited by the distance, because copying from the dictionary is defined as if the copy was performed byte by byte, keeping the distance constant.

Distances are logically 32-bit and distance 0 points to the most recently added byte in the dictionary.

The distance encoding starts with a 6-bit "distance slot", which determines how many further bits are needed.
Distances are decoded as a binary concatenation of, from most to least significant, two bits depending on the distance slot, some bits encoded with fixed 0.5 probability, and some context encoded bits, according to the following table (distance slots 0−3 directly encode distances 0−3).

{| class="wikitable defaultright"
|+ Distance encoding<ref name=lzma-sdk-format>{{cite web |title=LZMA Specification.7z in LZMA SDK |url=https://www.7-zip.org/sdk.html |website=7-zip.org}}</ref>
|-
! 6-bit distance slot
! Highest 2 bits
! Fixed 0.5 probability bits
! Context encoded bits
|-
| 0
| 00
| 0
| 0
|-
| 1
| 01
| 0
| 0
|-
| 2
| 10
| 0
| 0
|-
| 3
| 11
| 0
| 0
|-
| 4
| 10
| 0
| 1
|-
| 5
| 11
| 0
| 1
|-
| 6
| 10
| 0
| 2
|-
| 7
| 11
| 0
| 2
|-
| 8
| 10
| 0
| 3
|-
| 9
| 11
| 0
| 3
|-
| 10
| 10
| 0
| 4
|-
| 11
| 11
| 0
| 4
|-
| 12
| 10
| 0
| 5
|-
| 13
| 11
| 0
| 5
|-
| 14–62 (even)
| 10
| slot / 2 − 5
| 4
|-
| 15–63 (odd)
| 11
| (slot − 1) / 2 − 5
|4
|}

== Decompression algorithm details ==
{{Original research|section|date=April 2012}}
No complete natural language specification of the compressed format seems to exist, other than the one attempted in the following text.

The description below is based on the compact [[XZ Utils|XZ]] Embedded decoder by Lasse Collin included in the Linux kernel source<ref>{{cite web
| url=https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/lib/xz/xz_dec_lzma2.c
| title=lib/xz/xz_dec_lzma2.c
| first1=Lasse
| last1=Collin
| first2=Igor
| last2=Pavlov
| access-date=2013-06-16}}</ref> from which the LZMA and LZMA2 algorithm details can be relatively easily deduced: thus, while citing source code as reference is not ideal, any programmer should be able to check the claims below with a few hours of work.

===Range coding of bits===

LZMA data is at the lowest level decoded one bit at a time by the range decoder, at the direction of the LZMA decoder.

Context-based range decoding is invoked by the LZMA algorithm passing it a reference to the "context", which consists of the unsigned 11-bit variable ''prob'' (typically implemented using a 16-bit data type) representing the predicted probability of the bit being 0, which is read and updated by the range decoder (and should be initialized to {{tmath|2^{10} }}, representing 0.5 probability).

Fixed probability range decoding instead assumes a 0.5 probability, but operates slightly differently from context-based range decoding.

The range decoder state consists of two unsigned 32-bit variables, ''range'' (representing the range size), and ''code'' (representing the encoded point within the range).

Initialization of the range decoder consists of setting ''range'' to {{math|2<sup>32</sup> − 1}}, and ''code'' to the 32-bit value starting at the second byte in the stream interpreted as big-endian; the first byte in the stream is completely ignored.

Normalization proceeds in this way:
# Shift both ''range'' and ''code'' left by 8 bits
# Read a byte from the compressed stream
# Set the least significant 8 bits of ''code'' to the byte value read

Context-based range decoding of a bit using the ''prob'' probability variable proceeds in this way:
# If ''range'' is less than {{tmath|2^{24} }}, perform normalization
# Set ''bound'' to {{tmath|\lfloor range / 2^{11} \rfloor \times prob}}
# If ''code'' is less than ''bound'':
## Set ''range'' to ''bound''
## Set ''prob'' to ''prob'' + {{tmath|\lfloor 2^{11} - prob \rfloor / 2^5}}
## Return bit 0
# Otherwise (if ''code'' is greater than or equal to the ''bound''):
## Set ''range'' to ''range'' &minus; ''bound''
## Set ''code'' to ''code'' &minus; ''bound''
## Set ''prob'' to {{tmath|prob - \lfloor prob / 2^5 \rfloor }}
## Return bit 1

Fixed-probability range decoding of a bit proceeds in this way:
# If ''range'' is less than {{tmath|2^{24} }}, perform normalization
# Set ''range'' to {{tmath|\lfloor range / 2 \rfloor}}
# If ''code'' is less than ''range'':
## Return bit 0
# Otherwise (if ''code'' is greater or equal than ''range''):
## Set ''code'' to ''code'' &minus; ''range''
## Return bit 1

The Linux kernel implementation of fixed-probability decoding in <code>rc_direct()</code>, for performance reasons, does not include a conditional branch, but instead subtracts ''range'' from ''code'' unconditionally. The resulting sign bit is used to both decide the bit to return and to generate a mask that is combined with ''code'' and added to ''range''.

Note that:
# The division by {{tmath|2^{11} }} when computing ''bound'' and floor operation is done before the multiplication, not after (apparently to avoid requiring fast hardware support for 32-bit multiplication with a 64-bit result)
# Fixed probability decoding is not strictly equivalent to context-based range decoding with any ''prob'' value, due to the fact that context-based range decoding discards the lower 11 bits of ''range'' before multiplying by ''prob'' as just described, while fixed probability decoding only discards the last bit

===Range coding of integers ===

The range decoder also provides the bit-tree, reverse bit-tree and fixed probability integer decoding facilities, which are used to decode integers, and generalize the single-bit decoding described above.
To decode unsigned integers less than ''limit'', an array of {{math|(''limit'' − 1)}} 11-bit probability variables is provided, which are conceptually arranged as the internal nodes of a complete binary tree with ''limit'' leaves.

Non-reverse bit-tree decoding works by keeping a pointer to the tree of variables, which starts at the root. As long as the pointer does not point to a leaf, a bit is decoded using the variable indicated by the pointer, and the pointer is moved to either the left or right children depending on whether the bit is 0 or 1; when the pointer points to a leaf, the number associated with the leaf is returned.

Non-reverse bit-tree decoding thus happens from most significant to least significant bit, stopping when only one value in the valid range is possible (this conceptually allows to have range sizes that are not powers of two, even though LZMA does not make use of this).

Reverse bit-tree decoding instead decodes from least significant bit to most significant bits, and thus only supports ranges that are powers of two, and always decodes the same number of bits. It is equivalent to performing non-reverse bittree decoding with a power of two ''limit'', and reversing the last {{math|log{{sub|2}}(''limit'')}} bits of the result.

In the {{mono|rc_bittree}} function in the Linux kernel, integers are actually returned in the {{math|[''limit'', 2 × ''limit'')}} range (with ''limit'' added to the conceptual value), and the variable at index 0 in the array is unused, while the one at index 1 is the root, and the left and right children indices are computed as 2''i'' and 2''i'' + 1. The {{mono|rc_bittree_reverse}} function instead adds integers in the {{math|[0, ''limit'')}} range to a caller-provided variable, where ''limit'' is implicitly represented by its logarithm, and has its own independent implementation for efficiency reasons.

Fixed probability integer decoding simply performs fixed probability bit decoding repeatedly, reading bits from the most to the least significant.

=== LZMA configuration ===
The LZMA decoder is configured by an {{mono|''lclppb''}} "properties" byte and a dictionary size. The value of the {{mono|''lclppb''}} byte is <code>''lc'' + ''lp'' * 9 + ''pb'' * 9 * 5</code>, where:
* {{mono|''lc''}} is the number of high bits of the previous byte to use as a context for literal encoding (the default value used by the LZMA SDK is 3)
* {{mono|''lp''}} is the number of low bits of the dictionary position to include in {{mono|''literal_pos_state''}} (the default value used by the LZMA SDK is 0)
* {{mono|''pb''}} is the number of low bits of the dictionary position to include in {{mono|''pos_state''}} (the default value used by the LZMA SDK is 2)

In non-LZMA2 streams, {{mono|''lc''}} must not be greater than 8, and {{mono|''lp''}} and {{mono|''pb''}} must not be greater than 4; this results in a range of 0 to 224. In LZMA2 streams, <code>''lc'' + ''lp''</code> and {{mono|''pb''}} must not be greater than 4; this provides a much larger set of impossible values.

In the 7-zip LZMA file format, configuration is performed by a header containing the "properties" byte followed by the 32-bit little-endian dictionary size in bytes. In LZMA2, the properties byte can optionally be changed at the start of LZMA2 LZMA packets, while the dictionary size is specified in the LZMA2 header as later described.

=== LZMA coding contexts ===

The LZMA packet format has already been described, and this section specifies how LZMA statistically models the LZ-encoded streams, or in other words which probability variables are passed to the range decoder to decode each bit.

Those probability variables are implemented as multi-dimensional arrays; before introducing them, a few values that are used as indices in these multidimensional arrays are defined.

The {{mono|''state''}} value is conceptually based on which of the patterns in the following table match the latest 2–4 packet types seen, and is implemented as a state machine state updated according to the transition table listed in the table every time a packet is output.

The initial state is 0, and thus packets before the beginning are assumed to be LIT packets.
{| class="wikitable" border="1"
|-
! state
! colspan="4" | previous packets
! colspan="4" | next state when next packet is
|-
!
! 4th previous
! 3rd previous
! 2nd previous
! previous
! LIT
! MATCH
! LONGREP[*]
! SHORTREP
|-
| 0
|
| LIT
| LIT
| LIT
| 0
| 7
| 8
| 9
|-
| 1
|
| MATCH
| LIT
| LIT
| 0
| 7
| 8
| 9
|-
| rowspan="2" | 2
|
| LONGREP[*]
| rowspan="2" | LIT
| rowspan="2" | LIT
| rowspan="2" | 0
| rowspan="2" | 7
| rowspan="2" | 8
| rowspan="2" | 9
|-
| *MATCH
| SHORTREP
|-
| 3
| LIT
| SHORTREP
| LIT
| LIT
| 0
| 7
| 8
| 9
|-
| 4
|
|
| MATCH
| LIT
| 1
| 7
| 8
| 9
|-
| rowspan="2" | 5
| rowspan="2" |
|
| LONGREP[*]
| rowspan="2" | LIT
| rowspan="2" | 2
| rowspan="2" | 7
| rowspan="2" | 8
| rowspan="2" | 9
|-
| *MATCH
| SHORTREP
|-
| 6
|
| LIT
| SHORTREP
| LIT
| 3
| 7
| 8
| 9
|-
| 7
|
|
| LIT
| MATCH
| 4
| 10
| 11
| 11
|-
| 8
|
|
| LIT
| LONGREP[*]
| 5
| 10
| 11
| 11
|-
| 9
|
|
| LIT
| SHORTREP
| 6
| 10
| 11
| 11
|-
| 10
|
|
| *MATCH
| MATCH
| 4
| 10
| 11
| 11
|-
| 11
|
|
| *MATCH
| *REP
| 5
| 10
| 11
| 11
|}

The {{mono|''pos_state''}} and {{mono|''literal_pos_state''}} values consist of respectively the {{mono|''pb''}} and {{mono|''lp''}} (up to 4, from the LZMA header or LZMA2 properties packet) least significant bits of the dictionary position (the number of bytes coded since the last dictionary reset modulo the dictionary size). Note that the dictionary size is normally the multiple of a large power of 2, so these values are equivalently described as the least significant bits of the number of uncompressed bytes seen since the last dictionary reset.

The {{mono|''prev_byte_lc_msbs''}} value is set to the {{mono|''lc''}} (up to 4, from the LZMA header or LZMA2 properties packet) most significant bits of the previous uncompressed byte.

The {{mono|''is_REP''}} value denotes whether a packet that includes a length is a LONGREP rather than a MATCH.

The {{mono|''match_byte''}} value is the byte that would have been decoded if a SHORTREP packet had been used (in other words, the byte found at the dictionary at the last used distance); it is only used just after a *MATCH packet.

{{mono|''literal_bit_mode''}} is an array of 8 values in the 0–2 range, one for each bit position in a byte, which are 1 or 2 if the previous packet was a *MATCH and it is either the most significant bit position or all the more significant bits in the literal to encode/decode are equal to the bits in the corresponding positions in {{mono|''match_byte''}}, while otherwise it is 0; the choice between the 1 or 2 values depends on the value of the bit at the same position in {{mono|''match_byte''}}.

The literal/Literal set of variables can be seen as a "pseudo-bit-tree" similar to a bit-tree but with 3 variables instead of 1 in every node, chosen depending on the {{mono|''literal_bit_mode''}} value at the bit position of the next bit to decode after the bit-tree context denoted by the node.

The claim, found in some sources, that literals after a *MATCH are coded as the XOR of the byte value with {{mono|''match_byte''}} is incorrect; they are instead coded simply as their byte value, but using the pseudo-bit-tree just described and the additional context listed in the table below.

The probability variable groups used in LZMA are those:
{| class="wikitable" border="1"
|-
! XZ name
! LZMA SDK name
! Parameterized by
! Used when
! Coding mode
! If bit 0 then
! If bit 1 then
|-
| {{mono|is_match}}
| {{mono|IsMatch}}
| {{mono|''state''}}, {{mono|''pos_state''}}
| packet start
| bit
| LIT
| *MATCH
|-
| {{mono|is_rep}}
| {{mono|IsRep}}
| {{mono|''state''}}
| after bit sequence 1
| bit
| MATCH
| *REP
|-
| {{mono|is_rep0}}
| {{mono|IsRepG0}}
| {{mono|''state''}}
| after bit sequence 11
| bit
| SHORTREP/{{nowrap|LONGREP[0]}}
| {{nowrap|LONGREP[1–3]}}
|-
| {{mono|is_rep0_long}}
| {{mono|IsRep0Long}}
| {{mono|''state''}}, {{mono|''pos_state''}}
| after bit sequence 110
| bit
| SHORTREP
| LONGREP[0]
|-
| {{mono|is_rep1}}
| {{mono|IsRepG1}}
| {{mono|''state''}}
| after bit sequence 111
| bit
| LONGREP[1]
| LONGREP[2/3]
|-
| {{mono|is_rep2}}
| {{mono|IsRepG2}}
| {{mono|''state''}}
| after bit sequence 1111
| bit
| LONGREP[2]
| LONGREP[3]
|-
| {{mono|literal}}
| {{mono|Literal}}
| {{mono|''prev_byte_lc_msbs''}}, {{mono|''literal_pos_state''}}, {{nowrap|<code>''literal_bit_mode''[bit position]</code>}}, bit-tree context
| after bit sequence 0
| 256 values pseudo-bit-tree
| colspan="2" | literal byte value
|-
| {{mono|dist_slot}}
| {{mono|PosSlot}}
| <code>min(''match_length'', 5)</code>, bit-tree context
| distance: start
| 64 values bit-tree
| colspan="2" | distance slot
|-
| {{mono|dist_special}}
| {{mono|SpecPos}}
| {{mono|''distance_slot''}}, reverse bit-tree context
| distance: 4–13 distance slots
| {{nowrap|<code>((''distance_slot'' >> 1) − 1)</code>}}-bit reverse bit-tree
| colspan="2" | low bits of distance
|-
| {{mono|dist_align}}
| {{mono|Align}}
| reverse bit-tree context
| distance: 14+ distance slots, after fixed probability bits
| 4-bit reverse bit-tree
| colspan="2" | low bits of distance
|-
| {{mono|len_dec.choice}}
| {{mono|LenChoice}}
| {{mono|''is_REP''}}
| match length: start
| bit
| 2–9 length
| 10+ length
|-
| {{mono|len_dec.choice2}}
| {{mono|LenChoice2}}
| {{mono|''is_REP''}}
| match length: after bit sequence 1
| bit
| 10–17 length
| 18+ length
|-
| {{mono|len_dec.low}}
| {{mono|LenLow}}
| {{mono|''is_REP''}}, {{mono|''pos_state''}}, bit-tree context
| match length: after bit sequence 0
| 8 values bit-tree
| colspan="2" | low bits of length
|-
| {{mono|len_dec.mid}}
| {{mono|LenMid}}
| {{mono|''is_REP''}}, {{mono|''pos_state''}}, bit-tree context
| match length: after bit sequence 10
| 8 values bit-tree
| colspan="2" | middle bits of length
|-
| {{mono|len_dec.high}}
| {{mono|LenHigh}}
| {{mono|''is_REP''}}, bit-tree context
| match length: after bit sequence 11
| 256 values bit-tree
| colspan="2" | high bits of length
|}

=== LZMA2 format ===
The LZMA2 container supports multiple runs of compressed LZMA data and uncompressed data. Each LZMA compressed run can have a different LZMA configuration and dictionary. This improves the compression of partially or completely incompressible files and allows multithreaded compression and multithreaded decompression by breaking the file into runs that can be compressed or decompressed independently in parallel.
Criticism of changes in LZMA2 over LZMA include header fields not being covered by CRCs,
and parallel decompression not being possible in practice.<ref name=xz-inadequate />

The LZMA2 header consists of a byte indicating the dictionary size:
* 40 indicates a 4 GB − 1 dictionary size
* Even values less than 40 indicate a 2<sup>''v''/2 + 12</sup> bytes dictionary size
* Odd values less than 40 indicate a 3×2<sup>(''v'' − 1)/2 + 11</sup> bytes dictionary size
* Values higher than 40 are invalid

LZMA2 data consists of packets starting with a control byte, with the following values:
* 0 denotes the end of the file
* 1 denotes a dictionary reset followed by an uncompressed chunk
* 2 denotes an uncompressed chunk without a dictionary reset
* 3–0x7f are invalid values
* 0x80–0xff denotes an LZMA chunk, where the lowest 5 bits are used as bit 16–20 of the uncompressed size minus one, and bit 5–6 indicates what should be reset

Bits 5–6 for LZMA chunks can be:
* 0: nothing reset
* 1: state reset
* 2: state reset, properties reset using properties byte
* 3: state reset,  properties reset using properties byte, dictionary reset

LZMA state resets cause a reset of all LZMA state except the dictionary, and specifically:
* The range coder
* The ''state'' value
* The last distances for repeated matches
* All LZMA probabilities

Uncompressed chunks consist of:
* A 16-bit big-endian value encoding the data size minus one
* The data to be copied verbatim into the dictionary and the output

LZMA chunks consist of:
* A 16-bit big-endian value encoding the low 16 bits of the uncompressed size minus one
* A 16-bit big-endian value encoding the compressed size minus one
* A properties/lclppb byte if bit 6 in the control byte is set
* The LZMA compressed data, starting with the 5 bytes (of which the first is ignored) used to initialize the range coder (which are included in the compressed size)

=== xz and 7z formats ===

The .[[XZ Utils|xz]] format, which can contain LZMA2 data, is documented at ''tukaani.org'',<ref>{{cite web
| url=http://tukaani.org/xz/xz-file-format.txt
| title=The .xz File Format
| date=2009-08-27
| access-date=2013-06-16}}</ref> while the .7z file format, which can contain either LZMA or LZMA2 data, is documented in the 7zformat.txt file contained in the LZMA SDK.<ref name="LZMA_SDK">{{cite web
| url=http://7-zip.org/sdk.html
| title=LZMA SDK (Software Development Kit)
| year=2013
| author=Igor Pavlov
| access-date=2013-06-16
}}</ref>

== 7-Zip reference implementation ==
The LZMA implementation extracted from [[7-Zip]] is available as LZMA SDK. It was originally dual-licensed under both the [[GNU Lesser General Public License|GNU LGPL]] and [[Common Public License]],<ref>{{cite web | url = https://sourceforge.net/projects/sevenzip/files/LZMA%20SDK/4.23/ | title = Browse /LZMA SDK/4.23 | access-date = 2014-02-12 | publisher = [[SourceForge]]}}</ref> with an additional special exception for linked binaries, but was placed by [[Igor Pavlov (programmer)|Igor Pavlov]] in the [[public domain]] on December 2, 2008, with the release of version 4.62.<ref name="LZMA_SDK"/>

LZMA2 compression, which is an improved version of LZMA,<ref>{{cite web
| url=http://www.jrsoftware.org/ishelp/index.php?topic=setup_compression
| title=Inno Setup Help
| quote=LZMA2 is a modified version of LZMA that offers a better compression ratio for uncompressible data (random data expands about 0.005%, compared to 1.35% with original LZMA), and optionally can compress multiple parts of large files in parallel, greatly increasing compression speed but with a possible reduction in compression ratio.
| publisher=jrsoftware.org
| access-date=2013-06-16}}</ref> is now the default compression method for the .7z format, starting with version 9.30 on October 26, 2012.<ref>{{cite web
| url=http://www.7-zip.org/history.txt
| title=HISTORY of the 7-Zip
| date=2012-10-26
| access-date=2013-06-16
}}</ref>

The reference [[Open-source license|open source]] LZMA compression library was originally written in [[C++]] but has been ported to [[C (programming language)|ANSI C]], [[C Sharp (programming language)|C#]], and [[Java (programming language)|Java]].<ref name="LZMA_SDK" /> There are also third-party [[Python (programming language)|Python]] bindings for the C++ library,<ref>{{cite web
| url=http://www.joachim-bauch.de/projects/pylzma/
| title=PyLZMA – Platform independent python bindings for the LZMA compression library.
| first=Joachim
| last=Bauch
| date=2010-04-07
| access-date=2013-06-16}}</ref> as well as ports of LZMA to [[Pascal (programming language)|Pascal]],<ref>{{cite web
| url=http://www.birtles.org.uk/programming
| title=Programming Help: Pascal LZMA SDK
| date=2006-06-13
| first=Alan
| last=Birtles
| access-date=2013-06-16
}}</ref> [[Go (programming language)|Go]]<ref>
{{cite web
 |url          = http://lzma.googlecode.com/
 |archive-url  = http://webarchive.loc.gov/all/20160921065754/http://lzma.googlecode.com/
 |url-status   = dead
 |archive-date = 2016-09-21
 |title        = compress/lzma package for Go 1
 |first        = Andrei
 |last         = Vieru
 |date         = 2012-06-28
 |access-date   = 2013-06-16
}}</ref> and [[Ada (programming language)|Ada]].<ref>{{cite web
| url=https://unzip-ada.sourceforge.net/
| title=Zip-Ada}}</ref>

The 7-Zip implementation uses several variants of [[hash chain]]s, [[binary tree]]s and [[Patricia tree]]s as the basis for its dictionary search algorithm.

In addition to LZMA, the SDK and 7-Zip also implements multiple [[7z#Pre-processing filters|preprocessing filter]]s intended to improve compression, ranging from simple [[delta encoding]] (for images) and BCJ for executable code. It also provides some other compression algorithms used in 7z.

Decompression-only code for LZMA generally compiles to around 5&nbsp;KB, and the amount of RAM required during decompression is principally determined by the size of the [[LZ77 and LZ78|sliding window]] used during compression. Small code size and relatively low memory overhead, particularly with smaller dictionary lengths, and free source code make the LZMA decompression algorithm well-suited to [[Embedded system|embedded]] applications.

== Other implementations ==
In addition to the 7-Zip reference implementation, the following support the LZMA format.
* [[XZ Utils|xz]]: a streaming implementation that contains a [[gzip]]-like command line tool, supporting both LZMA and LZMA2 in its xz file format. It made its way into several software of the [[Unix-like]] world with its high performance (compared to [[bzip2]]) and small size (compared to [[gzip]]).<ref name=gzip_bzip_lzma_bench/> The [[Linux kernel]], [[dpkg]] and [[RPM Package Manager|RPM]] systems contains xz code, and many software distributors like [[Linux kernel|kernel.org]], [[Debian]]<ref name=dpkg_use_xz>{{cite web|author1=Guillem Jover|title=Accepted dpkg 1.17.0 (source amd64 all)|url=http://packages.qa.debian.org/d/dpkg/news/20130727T040302Z.html|website=Debian Package QA|access-date=2015-10-21}}</ref> and [[Fedora (operating system)|Fedora]] now use xz for compressing their releases.
* [[lzip]]: another LZMA implementation mostly for Unix-like systems that is an alternative to xz.<ref name=lzip_bench>{{cite web|last1=Diaz|first1=Diaz|title=Lzip Benchmarks|url=http://lzip.nongnu.org/lzip_benchmark.html|publisher=LZIP (nongnu)}}</ref> It features a simpler file format with easier error recovery.
* [[Zip (file format)|ZIPX]]: an extension to the [[Zip (file format)|ZIP]] compression format that was created by [[WinZip]] starting with version 12.1.  It also can use various other compression methods such as [[bzip2|BZip]] and [[Prediction by partial matching|PPMd]].<ref name=zipx>{{cite web|title=What is a Zipx File?|url=http://kb.winzip.com/kb/entry/7|publisher=WinZip.com|access-date=2016-03-14}}</ref>

== References==
{{Reflist|30em}}

== External links ==
* [http://www.7-zip.org/ Official home page]
* [http://www.nongnu.org/lzip/manual/lzip_manual.html#File-format Lzip format specification]
* [http://tukaani.org/xz/format.html XZ format specification]
* [http://www.7-zip.org/sdk.html LZMA SDK (Software Development Kit)]
* [http://tukaani.org/xz LZMA Utils = XZ Utils]
* [https://web.archive.org/web/20100430180036/http://nullprogram.com/blog/2010/04/16 Windows Binaries for XZ Utils]
* [https://pmwiki.xaver.me/drdoswiki/index.php?n=Main.Compress Data compression, Compressors & Archivers]

{{Archive formats}}
{{Compression Methods}}

[[Category:Lossless compression algorithms]]
[[Category:Israeli inventions]]
[[Category:Data compression]]