[6] LZMA uses a 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 encoder, using a complex model to make a probability prediction of each bit.
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 Embedded decoder by Lasse Collin included in the Linux kernel source[9] 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.
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
Non-reverse bit-tree decoding works by keeping a pointer to the tree of variables, which starts at the root.
The LZMA decoder is configured by an lclppb "properties" byte and a dictionary size.
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.
The prev_byte_lc_msbs value is set to the lc (up to 4, from the LZMA header or LZMA2 properties packet) most significant bits of the previous uncompressed byte.
The claim, found in some sources, that literals after a *MATCH are coded as the XOR of the byte value with 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.
Criticism of LZMA2's changes over LZMA include header fields not being covered by CRCs, and parallel decompression not being possible in practice.
[14] The reference open source LZMA compression library was originally written in C++ but has been ported to ANSI C, C#, and Java.
[11] There are also third-party Python bindings for the C++ library, as well as ports of LZMA to Pascal, Go and Ada.
In addition to LZMA, the SDK and 7-Zip also implements multiple preprocessing filters intended to improve compression, ranging from simple delta encoding (for images) and BCJ for executable code.
Decompression-only code for LZMA generally compiles to around 5 KB, and the amount of RAM required during decompression is principally determined by the size of the 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 applications.