--- /dev/null
+LZMA specification (DRAFT version)\r
+----------------------------------\r
+\r
+Author: Igor Pavlov\r
+Date: 2015-06-14\r
+\r
+This specification defines the format of LZMA compressed data and lzma file format.\r
+\r
+Notation \r
+--------\r
+\r
+We use the syntax of C++ programming language.\r
+We use the following types in C++ code:\r
+ unsigned - unsigned integer, at least 16 bits in size\r
+ int - signed integer, at least 16 bits in size\r
+ UInt64 - 64-bit unsigned integer\r
+ UInt32 - 32-bit unsigned integer\r
+ UInt16 - 16-bit unsigned integer\r
+ Byte - 8-bit unsigned integer\r
+ bool - boolean type with two possible values: false, true\r
+\r
+\r
+lzma file format\r
+================\r
+\r
+The lzma file contains the raw LZMA stream and the header with related properties.\r
+\r
+The files in that format use ".lzma" extension.\r
+\r
+The lzma file format layout:\r
+\r
+Offset Size Description\r
+\r
+ 0 1 LZMA model properties (lc, lp, pb) in encoded form\r
+ 1 4 Dictionary size (32-bit unsigned integer, little-endian)\r
+ 5 8 Uncompressed size (64-bit unsigned integer, little-endian)\r
+ 13 Compressed data (LZMA stream)\r
+\r
+LZMA properties:\r
+\r
+ name Range Description\r
+\r
+ lc [0, 8] the number of "literal context" bits\r
+ lp [0, 4] the number of "literal pos" bits\r
+ pb [0, 4] the number of "pos" bits\r
+dictSize [0, 2^32 - 1] the dictionary size \r
+\r
+The following code encodes LZMA properties:\r
+\r
+void EncodeProperties(Byte *properties)\r
+{\r
+ properties[0] = (Byte)((pb * 5 + lp) * 9 + lc);\r
+ Set_UInt32_LittleEndian(properties + 1, dictSize);\r
+}\r
+\r
+If the value of dictionary size in properties is smaller than (1 << 12),\r
+the LZMA decoder must set the dictionary size variable to (1 << 12).\r
+\r
+#define LZMA_DIC_MIN (1 << 12)\r
+\r
+ unsigned lc, pb, lp;\r
+ UInt32 dictSize;\r
+ UInt32 dictSizeInProperties;\r
+\r
+ void DecodeProperties(const Byte *properties)\r
+ {\r
+ unsigned d = properties[0];\r
+ if (d >= (9 * 5 * 5))\r
+ throw "Incorrect LZMA properties";\r
+ lc = d % 9;\r
+ d /= 9;\r
+ pb = d / 5;\r
+ lp = d % 5;\r
+ dictSizeInProperties = 0;\r
+ for (int i = 0; i < 4; i++)\r
+ dictSizeInProperties |= (UInt32)properties[i + 1] << (8 * i);\r
+ dictSize = dictSizeInProperties;\r
+ if (dictSize < LZMA_DIC_MIN)\r
+ dictSize = LZMA_DIC_MIN;\r
+ }\r
+\r
+If "Uncompressed size" field contains ones in all 64 bits, it means that\r
+uncompressed size is unknown and there is the "end marker" in stream,\r
+that indicates the end of decoding point.\r
+In opposite case, if the value from "Uncompressed size" field is not\r
+equal to ((2^64) - 1), the LZMA stream decoding must be finished after\r
+specified number of bytes (Uncompressed size) is decoded. And if there \r
+is the "end marker", the LZMA decoder must read that marker also.\r
+\r
+\r
+The new scheme to encode LZMA properties\r
+----------------------------------------\r
+\r
+If LZMA compression is used for some another format, it's recommended to\r
+use a new improved scheme to encode LZMA properties. That new scheme was\r
+used in xz format that uses the LZMA2 compression algorithm.\r
+The LZMA2 is a new compression algorithm that is based on the LZMA algorithm.\r
+\r
+The dictionary size in LZMA2 is encoded with just one byte and LZMA2 supports\r
+only reduced set of dictionary sizes:\r
+ (2 << 11), (3 << 11),\r
+ (2 << 12), (3 << 12),\r
+ ...\r
+ (2 << 30), (3 << 30),\r
+ (2 << 31) - 1\r
+\r
+The dictionary size can be extracted from encoded value with the following code:\r
+\r
+ dictSize = (p == 40) ? 0xFFFFFFFF : (((UInt32)2 | ((p) & 1)) << ((p) / 2 + 11));\r
+\r
+Also there is additional limitation (lc + lp <= 4) in LZMA2 for values of \r
+"lc" and "lp" properties:\r
+\r
+ if (lc + lp > 4)\r
+ throw "Unsupported properties: (lc + lp) > 4";\r
+\r
+There are some advantages for LZMA decoder with such (lc + lp) value\r
+limitation. It reduces the maximum size of tables allocated by decoder.\r
+And it reduces the complexity of initialization procedure, that can be \r
+important to keep high speed of decoding of big number of small LZMA streams.\r
+\r
+It's recommended to use that limitation (lc + lp <= 4) for any new format\r
+that uses LZMA compression. Note that the combinations of "lc" and "lp" \r
+parameters, where (lc + lp > 4), can provide significant improvement in \r
+compression ratio only in some rare cases.\r
+\r
+The LZMA properties can be encoded into two bytes in new scheme:\r
+\r
+Offset Size Description\r
+\r
+ 0 1 The dictionary size encoded with LZMA2 scheme\r
+ 1 1 LZMA model properties (lc, lp, pb) in encoded form\r
+\r
+\r
+The RAM usage \r
+=============\r
+\r
+The RAM usage for LZMA decoder is determined by the following parts:\r
+\r
+1) The Sliding Window (from 4 KiB to 4 GiB).\r
+2) The probability model counter arrays (arrays of 16-bit variables).\r
+3) Some additional state variables (about 10 variables of 32-bit integers).\r
+\r
+\r
+The RAM usage for Sliding Window\r
+--------------------------------\r
+\r
+There are two main scenarios of decoding:\r
+\r
+1) The decoding of full stream to one RAM buffer.\r
+\r
+ If we decode full LZMA stream to one output buffer in RAM, the decoder \r
+ can use that output buffer as sliding window. So the decoder doesn't \r
+ need additional buffer allocated for sliding window.\r
+\r
+2) The decoding to some external storage.\r
+\r
+ If we decode LZMA stream to external storage, the decoder must allocate\r
+ the buffer for sliding window. The size of that buffer must be equal \r
+ or larger than the value of dictionary size from properties of LZMA stream.\r
+\r
+In this specification we describe the code for decoding to some external\r
+storage. The optimized version of code for decoding of full stream to one\r
+output RAM buffer can require some minor changes in code.\r
+\r
+\r
+The RAM usage for the probability model counters\r
+------------------------------------------------\r
+\r
+The size of the probability model counter arrays is calculated with the \r
+following formula:\r
+\r
+size_of_prob_arrays = 1846 + 768 * (1 << (lp + lc))\r
+\r
+Each probability model counter is 11-bit unsigned integer.\r
+If we use 16-bit integer variables (2-byte integers) for these probability \r
+model counters, the RAM usage required by probability model counter arrays \r
+can be estimated with the following formula:\r
+\r
+ RAM = 4 KiB + 1.5 KiB * (1 << (lp + lc))\r
+\r
+For example, for default LZMA parameters (lp = 0 and lc = 3), the RAM usage is\r
+\r
+ RAM_lc3_lp0 = 4 KiB + 1.5 KiB * 8 = 16 KiB\r
+\r
+The maximum RAM state usage is required for decoding the stream with lp = 4 \r
+and lc = 8:\r
+\r
+ RAM_lc8_lp4 = 4 KiB + 1.5 KiB * 4096 = 6148 KiB\r
+\r
+If the decoder uses LZMA2's limited property condition \r
+(lc + lp <= 4), the RAM usage will be not larger than\r
+\r
+ RAM_lc_lp_4 = 4 KiB + 1.5 KiB * 16 = 28 KiB\r
+\r
+\r
+The RAM usage for encoder\r
+-------------------------\r
+\r
+There are many variants for LZMA encoding code.\r
+These variants have different values for memory consumption.\r
+Note that memory consumption for LZMA Encoder can not be \r
+smaller than memory consumption of LZMA Decoder for same stream.\r
+\r
+The RAM usage required by modern effective implementation of \r
+LZMA Encoder can be estimated with the following formula:\r
+\r
+ Encoder_RAM_Usage = 4 MiB + 11 * dictionarySize.\r
+\r
+But there are some modes of the encoder that require less memory.\r
+\r
+\r
+LZMA Decoding\r
+=============\r
+\r
+The LZMA compression algorithm uses LZ-based compression with Sliding Window\r
+and Range Encoding as entropy coding method.\r
+\r
+\r
+Sliding Window\r
+--------------\r
+\r
+LZMA uses Sliding Window compression similar to LZ77 algorithm.\r
+\r
+LZMA stream must be decoded to the sequence that consists\r
+of MATCHES and LITERALS:\r
+ \r
+ - a LITERAL is a 8-bit character (one byte).\r
+ The decoder just puts that LITERAL to the uncompressed stream.\r
+ \r
+ - a MATCH is a pair of two numbers (DISTANCE-LENGTH pair).\r
+ The decoder takes one byte exactly "DISTANCE" characters behind\r
+ current position in the uncompressed stream and puts it to \r
+ uncompressed stream. The decoder must repeat it "LENGTH" times.\r
+\r
+The "DISTANCE" can not be larger than dictionary size.\r
+And the "DISTANCE" can not be larger than the number of bytes in\r
+the uncompressed stream that were decoded before that match.\r
+\r
+In this specification we use cyclic buffer to implement Sliding Window\r
+for LZMA decoder:\r
+\r
+class COutWindow\r
+{\r
+ Byte *Buf;\r
+ UInt32 Pos;\r
+ UInt32 Size;\r
+ bool IsFull;\r
+\r
+public:\r
+ unsigned TotalPos;\r
+ COutStream OutStream;\r
+\r
+ COutWindow(): Buf(NULL) {}\r
+ ~COutWindow() { delete []Buf; }\r
+ \r
+ void Create(UInt32 dictSize)\r
+ {\r
+ Buf = new Byte[dictSize];\r
+ Pos = 0;\r
+ Size = dictSize;\r
+ IsFull = false;\r
+ TotalPos = 0;\r
+ }\r
+\r
+ void PutByte(Byte b)\r
+ {\r
+ TotalPos++;\r
+ Buf[Pos++] = b;\r
+ if (Pos == Size)\r
+ {\r
+ Pos = 0;\r
+ IsFull = true;\r
+ }\r
+ OutStream.WriteByte(b);\r
+ }\r
+\r
+ Byte GetByte(UInt32 dist) const\r
+ {\r
+ return Buf[dist <= Pos ? Pos - dist : Size - dist + Pos];\r
+ }\r
+\r
+ void CopyMatch(UInt32 dist, unsigned len)\r
+ {\r
+ for (; len > 0; len--)\r
+ PutByte(GetByte(dist));\r
+ }\r
+\r
+ bool CheckDistance(UInt32 dist) const\r
+ {\r
+ return dist <= Pos || IsFull;\r
+ }\r
+\r
+ bool IsEmpty() const\r
+ {\r
+ return Pos == 0 && !IsFull;\r
+ }\r
+};\r
+\r
+\r
+In another implementation it's possible to use one buffer that contains \r
+Sliding Window and the whole data stream after uncompressing.\r
+\r
+\r
+Range Decoder\r
+-------------\r
+\r
+LZMA algorithm uses Range Encoding (1) as entropy coding method.\r
+\r
+LZMA stream contains just one very big number in big-endian encoding.\r
+LZMA decoder uses the Range Decoder to extract a sequence of binary\r
+symbols from that big number.\r
+\r
+The state of the Range Decoder:\r
+\r
+struct CRangeDecoder\r
+{\r
+ UInt32 Range; \r
+ UInt32 Code;\r
+ InputStream *InStream;\r
+\r
+ bool Corrupted;\r
+}\r
+\r
+The notes about UInt32 type for the "Range" and "Code" variables:\r
+\r
+ It's possible to use 64-bit (unsigned or signed) integer type\r
+ for the "Range" and the "Code" variables instead of 32-bit unsigned,\r
+ but some additional code must be used to truncate the values to \r
+ low 32-bits after some operations.\r
+\r
+ If the programming language does not support 32-bit unsigned integer type \r
+ (like in case of JAVA language), it's possible to use 32-bit signed integer, \r
+ but some code must be changed. For example, it's required to change the code\r
+ that uses comparison operations for UInt32 variables in this specification.\r
+\r
+The Range Decoder can be in some states that can be treated as \r
+"Corruption" in LZMA stream. The Range Decoder uses the variable "Corrupted":\r
+\r
+ (Corrupted == false), if the Range Decoder has not detected any corruption.\r
+ (Corrupted == true), if the Range Decoder has detected some corruption.\r
+\r
+The reference LZMA Decoder ignores the value of the "Corrupted" variable.\r
+So it continues to decode the stream, even if the corruption can be detected\r
+in the Range Decoder. To provide the full compatibility with output of the \r
+reference LZMA Decoder, another LZMA Decoder implementations must also \r
+ignore the value of the "Corrupted" variable.\r
+\r
+The LZMA Encoder is required to create only such LZMA streams, that will not \r
+lead the Range Decoder to states, where the "Corrupted" variable is set to true.\r
+\r
+The Range Decoder reads first 5 bytes from input stream to initialize\r
+the state:\r
+\r
+bool CRangeDecoder::Init()\r
+{\r
+ Corrupted = false;\r
+ Range = 0xFFFFFFFF;\r
+ Code = 0;\r
+\r
+ Byte b = InStream->ReadByte();\r
+ \r
+ for (int i = 0; i < 4; i++)\r
+ Code = (Code << 8) | InStream->ReadByte();\r
+ \r
+ if (b != 0 || Code == Range)\r
+ Corrupted = true;\r
+ return b == 0;\r
+}\r
+\r
+The LZMA Encoder always writes ZERO in initial byte of compressed stream.\r
+That scheme allows to simplify the code of the Range Encoder in the \r
+LZMA Encoder. If initial byte is not equal to ZERO, the LZMA Decoder must\r
+stop decoding and report error.\r
+\r
+After the last bit of data was decoded by Range Decoder, the value of the\r
+"Code" variable must be equal to 0. The LZMA Decoder must check it by \r
+calling the IsFinishedOK() function:\r
+\r
+ bool IsFinishedOK() const { return Code == 0; }\r
+\r
+If there is corruption in data stream, there is big probability that\r
+the "Code" value will be not equal to 0 in the Finish() function. So that\r
+check in the IsFinishedOK() function provides very good feature for \r
+corruption detection.\r
+\r
+The value of the "Range" variable before each bit decoding can not be smaller \r
+than ((UInt32)1 << 24). The Normalize() function keeps the "Range" value in \r
+described range.\r
+\r
+#define kTopValue ((UInt32)1 << 24)\r
+\r
+void CRangeDecoder::Normalize()\r
+{\r
+ if (Range < kTopValue)\r
+ {\r
+ Range <<= 8;\r
+ Code = (Code << 8) | InStream->ReadByte();\r
+ }\r
+}\r
+\r
+Notes: if the size of the "Code" variable is larger than 32 bits, it's\r
+required to keep only low 32 bits of the "Code" variable after the change\r
+in Normalize() function.\r
+\r
+If the LZMA Stream is not corrupted, the value of the "Code" variable is\r
+always smaller than value of the "Range" variable.\r
+But the Range Decoder ignores some types of corruptions, so the value of\r
+the "Code" variable can be equal or larger than value of the "Range" variable\r
+for some "Corrupted" archives.\r
+\r
+\r
+LZMA uses Range Encoding only with binary symbols of two types:\r
+ 1) binary symbols with fixed and equal probabilities (direct bits)\r
+ 2) binary symbols with predicted probabilities\r
+\r
+The DecodeDirectBits() function decodes the sequence of direct bits:\r
+\r
+UInt32 CRangeDecoder::DecodeDirectBits(unsigned numBits)\r
+{\r
+ UInt32 res = 0;\r
+ do\r
+ {\r
+ Range >>= 1;\r
+ Code -= Range;\r
+ UInt32 t = 0 - ((UInt32)Code >> 31);\r
+ Code += Range & t;\r
+ \r
+ if (Code == Range)\r
+ Corrupted = true;\r
+ \r
+ Normalize();\r
+ res <<= 1;\r
+ res += t + 1;\r
+ }\r
+ while (--numBits);\r
+ return res;\r
+}\r
+\r
+\r
+The Bit Decoding with Probability Model\r
+---------------------------------------\r
+\r
+The task of Bit Probability Model is to estimate probabilities of binary\r
+symbols. And then it provides the Range Decoder with that information.\r
+The better prediction provides better compression ratio.\r
+The Bit Probability Model uses statistical data of previous decoded\r
+symbols.\r
+\r
+That estimated probability is presented as 11-bit unsigned integer value\r
+that represents the probability of symbol "0".\r
+\r
+#define kNumBitModelTotalBits 11\r
+\r
+Mathematical probabilities can be presented with the following formulas:\r
+ probability(symbol_0) = prob / 2048.\r
+ probability(symbol_1) = 1 - Probability(symbol_0) = \r
+ = 1 - prob / 2048 = \r
+ = (2048 - prob) / 2048\r
+where the "prob" variable contains 11-bit integer probability counter.\r
+\r
+It's recommended to use 16-bit unsigned integer type, to store these 11-bit\r
+probability values:\r
+\r
+typedef UInt16 CProb;\r
+\r
+Each probability value must be initialized with value ((1 << 11) / 2),\r
+that represents the state, where probabilities of symbols 0 and 1 \r
+are equal to 0.5:\r
+\r
+#define PROB_INIT_VAL ((1 << kNumBitModelTotalBits) / 2)\r
+\r
+The INIT_PROBS macro is used to initialize the array of CProb variables:\r
+\r
+#define INIT_PROBS(p) \\r
+ { for (unsigned i = 0; i < sizeof(p) / sizeof(p[0]); i++) p[i] = PROB_INIT_VAL; }\r
+\r
+\r
+The DecodeBit() function decodes one bit.\r
+The LZMA decoder provides the pointer to CProb variable that contains \r
+information about estimated probability for symbol 0 and the Range Decoder \r
+updates that CProb variable after decoding. The Range Decoder increases \r
+estimated probability of the symbol that was decoded:\r
+\r
+#define kNumMoveBits 5\r
+\r
+unsigned CRangeDecoder::DecodeBit(CProb *prob)\r
+{\r
+ unsigned v = *prob;\r
+ UInt32 bound = (Range >> kNumBitModelTotalBits) * v;\r
+ unsigned symbol;\r
+ if (Code < bound)\r
+ {\r
+ v += ((1 << kNumBitModelTotalBits) - v) >> kNumMoveBits;\r
+ Range = bound;\r
+ symbol = 0;\r
+ }\r
+ else\r
+ {\r
+ v -= v >> kNumMoveBits;\r
+ Code -= bound;\r
+ Range -= bound;\r
+ symbol = 1;\r
+ }\r
+ *prob = (CProb)v;\r
+ Normalize();\r
+ return symbol;\r
+}\r
+\r
+\r
+The Binary Tree of bit model counters\r
+-------------------------------------\r
+\r
+LZMA uses a tree of Bit model variables to decode symbol that needs\r
+several bits for storing. There are two versions of such trees in LZMA:\r
+ 1) the tree that decodes bits from high bit to low bit (the normal scheme).\r
+ 2) the tree that decodes bits from low bit to high bit (the reverse scheme).\r
+\r
+Each binary tree structure supports different size of decoded symbol\r
+(the size of binary sequence that contains value of symbol).\r
+If that size of decoded symbol is "NumBits" bits, the tree structure \r
+uses the array of (2 << NumBits) counters of CProb type. \r
+But only ((2 << NumBits) - 1) items are used by encoder and decoder.\r
+The first item (the item with index equal to 0) in array is unused.\r
+That scheme with unused array's item allows to simplify the code.\r
+\r
+unsigned BitTreeReverseDecode(CProb *probs, unsigned numBits, CRangeDecoder *rc)\r
+{\r
+ unsigned m = 1;\r
+ unsigned symbol = 0;\r
+ for (unsigned i = 0; i < numBits; i++)\r
+ {\r
+ unsigned bit = rc->DecodeBit(&probs[m]);\r
+ m <<= 1;\r
+ m += bit;\r
+ symbol |= (bit << i);\r
+ }\r
+ return symbol;\r
+}\r
+\r
+template <unsigned NumBits>\r
+class CBitTreeDecoder\r
+{\r
+ CProb Probs[(unsigned)1 << NumBits];\r
+\r
+public:\r
+\r
+ void Init()\r
+ {\r
+ INIT_PROBS(Probs);\r
+ }\r
+\r
+ unsigned Decode(CRangeDecoder *rc)\r
+ {\r
+ unsigned m = 1;\r
+ for (unsigned i = 0; i < NumBits; i++)\r
+ m = (m << 1) + rc->DecodeBit(&Probs[m]);\r
+ return m - ((unsigned)1 << NumBits);\r
+ }\r
+\r
+ unsigned ReverseDecode(CRangeDecoder *rc)\r
+ {\r
+ return BitTreeReverseDecode(Probs, NumBits, rc);\r
+ }\r
+};\r
+\r
+\r
+LZ part of LZMA \r
+---------------\r
+\r
+LZ part of LZMA describes details about the decoding of MATCHES and LITERALS.\r
+\r
+\r
+The Literal Decoding\r
+--------------------\r
+\r
+The LZMA Decoder uses (1 << (lc + lp)) tables with CProb values, where \r
+each table contains 0x300 CProb values:\r
+\r
+ CProb *LitProbs;\r
+\r
+ void CreateLiterals()\r
+ {\r
+ LitProbs = new CProb[(UInt32)0x300 << (lc + lp)];\r
+ }\r
+ \r
+ void InitLiterals()\r
+ {\r
+ UInt32 num = (UInt32)0x300 << (lc + lp);\r
+ for (UInt32 i = 0; i < num; i++)\r
+ LitProbs[i] = PROB_INIT_VAL;\r
+ }\r
+\r
+To select the table for decoding it uses the context that consists of\r
+(lc) high bits from previous literal and (lp) low bits from value that\r
+represents current position in outputStream.\r
+\r
+If (State > 7), the Literal Decoder also uses "matchByte" that represents \r
+the byte in OutputStream at position the is the DISTANCE bytes before \r
+current position, where the DISTANCE is the distance in DISTANCE-LENGTH pair\r
+of latest decoded match.\r
+\r
+The following code decodes one literal and puts it to Sliding Window buffer:\r
+\r
+ void DecodeLiteral(unsigned state, UInt32 rep0)\r
+ {\r
+ unsigned prevByte = 0;\r
+ if (!OutWindow.IsEmpty())\r
+ prevByte = OutWindow.GetByte(1);\r
+ \r
+ unsigned symbol = 1;\r
+ unsigned litState = ((OutWindow.TotalPos & ((1 << lp) - 1)) << lc) + (prevByte >> (8 - lc));\r
+ CProb *probs = &LitProbs[(UInt32)0x300 * litState];\r
+ \r
+ if (state >= 7)\r
+ {\r
+ unsigned matchByte = OutWindow.GetByte(rep0 + 1);\r
+ do\r
+ {\r
+ unsigned matchBit = (matchByte >> 7) & 1;\r
+ matchByte <<= 1;\r
+ unsigned bit = RangeDec.DecodeBit(&probs[((1 + matchBit) << 8) + symbol]);\r
+ symbol = (symbol << 1) | bit;\r
+ if (matchBit != bit)\r
+ break;\r
+ }\r
+ while (symbol < 0x100);\r
+ }\r
+ while (symbol < 0x100)\r
+ symbol = (symbol << 1) | RangeDec.DecodeBit(&probs[symbol]);\r
+ OutWindow.PutByte((Byte)(symbol - 0x100));\r
+ }\r
+\r
+\r
+The match length decoding\r
+-------------------------\r
+\r
+The match length decoder returns normalized (zero-based value) \r
+length of match. That value can be converted to real length of the match \r
+with the following code:\r
+\r
+#define kMatchMinLen 2\r
+\r
+ matchLen = len + kMatchMinLen;\r
+\r
+The match length decoder can return the values from 0 to 271.\r
+And the corresponded real match length values can be in the range \r
+from 2 to 273.\r
+\r
+The following scheme is used for the match length encoding:\r
+\r
+ Binary encoding Binary Tree structure Zero-based match length \r
+ sequence (binary + decimal):\r
+\r
+ 0 xxx LowCoder[posState] xxx\r
+ 1 0 yyy MidCoder[posState] yyy + 8\r
+ 1 1 zzzzzzzz HighCoder zzzzzzzz + 16\r
+\r
+LZMA uses bit model variable "Choice" to decode the first selection bit.\r
+\r
+If the first selection bit is equal to 0, the decoder uses binary tree \r
+ LowCoder[posState] to decode 3-bit zero-based match length (xxx).\r
+\r
+If the first selection bit is equal to 1, the decoder uses bit model \r
+ variable "Choice2" to decode the second selection bit.\r
+\r
+ If the second selection bit is equal to 0, the decoder uses binary tree \r
+ MidCoder[posState] to decode 3-bit "yyy" value, and zero-based match\r
+ length is equal to (yyy + 8).\r
+\r
+ If the second selection bit is equal to 1, the decoder uses binary tree \r
+ HighCoder to decode 8-bit "zzzzzzzz" value, and zero-based \r
+ match length is equal to (zzzzzzzz + 16).\r
+\r
+LZMA uses "posState" value as context to select the binary tree \r
+from LowCoder and MidCoder binary tree arrays:\r
+\r
+ unsigned posState = OutWindow.TotalPos & ((1 << pb) - 1);\r
+\r
+The full code of the length decoder:\r
+\r
+class CLenDecoder\r
+{\r
+ CProb Choice;\r
+ CProb Choice2;\r
+ CBitTreeDecoder<3> LowCoder[1 << kNumPosBitsMax];\r
+ CBitTreeDecoder<3> MidCoder[1 << kNumPosBitsMax];\r
+ CBitTreeDecoder<8> HighCoder;\r
+\r
+public:\r
+\r
+ void Init()\r
+ {\r
+ Choice = PROB_INIT_VAL;\r
+ Choice2 = PROB_INIT_VAL;\r
+ HighCoder.Init();\r
+ for (unsigned i = 0; i < (1 << kNumPosBitsMax); i++)\r
+ {\r
+ LowCoder[i].Init();\r
+ MidCoder[i].Init();\r
+ }\r
+ }\r
+\r
+ unsigned Decode(CRangeDecoder *rc, unsigned posState)\r
+ {\r
+ if (rc->DecodeBit(&Choice) == 0)\r
+ return LowCoder[posState].Decode(rc);\r
+ if (rc->DecodeBit(&Choice2) == 0)\r
+ return 8 + MidCoder[posState].Decode(rc);\r
+ return 16 + HighCoder.Decode(rc);\r
+ }\r
+};\r
+\r
+The LZMA decoder uses two instances of CLenDecoder class.\r
+The first instance is for the matches of "Simple Match" type,\r
+and the second instance is for the matches of "Rep Match" type:\r
+\r
+ CLenDecoder LenDecoder;\r
+ CLenDecoder RepLenDecoder;\r
+\r
+\r
+The match distance decoding\r
+---------------------------\r
+\r
+LZMA supports dictionary sizes up to 4 GiB minus 1.\r
+The value of match distance (decoded by distance decoder) can be \r
+from 1 to 2^32. But the distance value that is equal to 2^32 is used to\r
+indicate the "End of stream" marker. So real largest match distance \r
+that is used for LZ-window match is (2^32 - 1).\r
+\r
+LZMA uses normalized match length (zero-based length) \r
+to calculate the context state "lenState" do decode the distance value:\r
+\r
+#define kNumLenToPosStates 4\r
+\r
+ unsigned lenState = len;\r
+ if (lenState > kNumLenToPosStates - 1)\r
+ lenState = kNumLenToPosStates - 1;\r
+\r
+The distance decoder returns the "dist" value that is zero-based value \r
+of match distance. The real match distance can be calculated with the\r
+following code:\r
+ \r
+ matchDistance = dist + 1; \r
+\r
+The state of the distance decoder and the initialization code: \r
+\r
+ #define kEndPosModelIndex 14\r
+ #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))\r
+ #define kNumAlignBits 4\r
+\r
+ CBitTreeDecoder<6> PosSlotDecoder[kNumLenToPosStates];\r
+ CProb PosDecoders[1 + kNumFullDistances - kEndPosModelIndex];\r
+ CBitTreeDecoder<kNumAlignBits> AlignDecoder;\r
+\r
+ void InitDist()\r
+ {\r
+ for (unsigned i = 0; i < kNumLenToPosStates; i++)\r
+ PosSlotDecoder[i].Init();\r
+ AlignDecoder.Init();\r
+ INIT_PROBS(PosDecoders);\r
+ }\r
+\r
+At first stage the distance decoder decodes 6-bit "posSlot" value with bit\r
+tree decoder from PosSlotDecoder array. It's possible to get 2^6=64 different \r
+"posSlot" values.\r
+\r
+ unsigned posSlot = PosSlotDecoder[lenState].Decode(&RangeDec);\r
+\r
+The encoding scheme for distance value is shown in the following table:\r
+\r
+posSlot (decimal) /\r
+ zero-based distance (binary)\r
+ 0 0\r
+ 1 1\r
+ 2 10\r
+ 3 11\r
+\r
+ 4 10 x\r
+ 5 11 x\r
+ 6 10 xx\r
+ 7 11 xx\r
+ 8 10 xxx\r
+ 9 11 xxx\r
+10 10 xxxx\r
+11 11 xxxx\r
+12 10 xxxxx\r
+13 11 xxxxx\r
+\r
+14 10 yy zzzz\r
+15 11 yy zzzz\r
+16 10 yyy zzzz\r
+17 11 yyy zzzz\r
+...\r
+62 10 yyyyyyyyyyyyyyyyyyyyyyyyyy zzzz\r
+63 11 yyyyyyyyyyyyyyyyyyyyyyyyyy zzzz\r
+\r
+where \r
+ "x ... x" means the sequence of binary symbols encoded with binary tree and \r
+ "Reverse" scheme. It uses separated binary tree for each posSlot from 4 to 13.\r
+ "y" means direct bit encoded with range coder.\r
+ "zzzz" means the sequence of four binary symbols encoded with binary\r
+ tree with "Reverse" scheme, where one common binary tree "AlignDecoder"\r
+ is used for all posSlot values.\r
+\r
+If (posSlot < 4), the "dist" value is equal to posSlot value.\r
+\r
+If (posSlot >= 4), the decoder uses "posSlot" value to calculate the value of\r
+ the high bits of "dist" value and the number of the low bits.\r
+\r
+ If (4 <= posSlot < kEndPosModelIndex), the decoder uses bit tree decoders.\r
+ (one separated bit tree decoder per one posSlot value) and "Reverse" scheme.\r
+ In this implementation we use one CProb array "PosDecoders" that contains \r
+ all CProb variables for all these bit decoders.\r
+ \r
+ if (posSlot >= kEndPosModelIndex), the middle bits are decoded as direct \r
+ bits from RangeDecoder and the low 4 bits are decoded with a bit tree \r
+ decoder "AlignDecoder" with "Reverse" scheme.\r
+\r
+The code to decode zero-based match distance:\r
+ \r
+ unsigned DecodeDistance(unsigned len)\r
+ {\r
+ unsigned lenState = len;\r
+ if (lenState > kNumLenToPosStates - 1)\r
+ lenState = kNumLenToPosStates - 1;\r
+ \r
+ unsigned posSlot = PosSlotDecoder[lenState].Decode(&RangeDec);\r
+ if (posSlot < 4)\r
+ return posSlot;\r
+ \r
+ unsigned numDirectBits = (unsigned)((posSlot >> 1) - 1);\r
+ UInt32 dist = ((2 | (posSlot & 1)) << numDirectBits);\r
+ if (posSlot < kEndPosModelIndex)\r
+ dist += BitTreeReverseDecode(PosDecoders + dist - posSlot, numDirectBits, &RangeDec);\r
+ else\r
+ {\r
+ dist += RangeDec.DecodeDirectBits(numDirectBits - kNumAlignBits) << kNumAlignBits;\r
+ dist += AlignDecoder.ReverseDecode(&RangeDec);\r
+ }\r
+ return dist;\r
+ }\r
+\r
+\r
+\r
+LZMA Decoding modes\r
+-------------------\r
+\r
+There are 2 types of LZMA streams:\r
+\r
+1) The stream with "End of stream" marker.\r
+2) The stream without "End of stream" marker.\r
+\r
+And the LZMA Decoder supports 3 modes of decoding:\r
+\r
+1) The unpack size is undefined. The LZMA decoder stops decoding after \r
+ getting "End of stream" marker. \r
+ The input variables for that case:\r
+ \r
+ markerIsMandatory = true\r
+ unpackSizeDefined = false\r
+ unpackSize contains any value\r
+\r
+2) The unpack size is defined and LZMA decoder supports both variants, \r
+ where the stream can contain "End of stream" marker or the stream is\r
+ finished without "End of stream" marker. The LZMA decoder must detect \r
+ any of these situations.\r
+ The input variables for that case:\r
+ \r
+ markerIsMandatory = false\r
+ unpackSizeDefined = true\r
+ unpackSize contains unpack size\r
+\r
+3) The unpack size is defined and the LZMA stream must contain \r
+ "End of stream" marker\r
+ The input variables for that case:\r
+ \r
+ markerIsMandatory = true\r
+ unpackSizeDefined = true\r
+ unpackSize contains unpack size\r
+\r
+\r
+The main loop of decoder\r
+------------------------\r
+\r
+The main loop of LZMA decoder:\r
+\r
+Initialize the LZMA state.\r
+loop\r
+{\r
+ // begin of loop\r
+ Check "end of stream" conditions.\r
+ Decode Type of MATCH / LITERAL. \r
+ If it's LITERAL, decode LITERAL value and put the LITERAL to Window.\r
+ If it's MATCH, decode the length of match and the match distance. \r
+ Check error conditions, check end of stream conditions and copy\r
+ the sequence of match bytes from sliding window to current position\r
+ in window.\r
+ Go to begin of loop\r
+}\r
+\r
+The reference implementation of LZMA decoder uses "unpackSize" variable\r
+to keep the number of remaining bytes in output stream. So it reduces \r
+"unpackSize" value after each decoded LITERAL or MATCH.\r
+\r
+The following code contains the "end of stream" condition check at the start\r
+of the loop:\r
+\r
+ if (unpackSizeDefined && unpackSize == 0 && !markerIsMandatory)\r
+ if (RangeDec.IsFinishedOK())\r
+ return LZMA_RES_FINISHED_WITHOUT_MARKER;\r
+\r
+LZMA uses three types of matches:\r
+\r
+1) "Simple Match" - the match with distance value encoded with bit models.\r
+\r
+2) "Rep Match" - the match that uses the distance from distance\r
+ history table.\r
+\r
+3) "Short Rep Match" - the match of single byte length, that uses the latest \r
+ distance from distance history table.\r
+\r
+The LZMA decoder keeps the history of latest 4 match distances that were used \r
+by decoder. That set of 4 variables contains zero-based match distances and \r
+these variables are initialized with zero values:\r
+\r
+ UInt32 rep0 = 0, rep1 = 0, rep2 = 0, rep3 = 0;\r
+\r
+The LZMA decoder uses binary model variables to select type of MATCH or LITERAL:\r
+\r
+#define kNumStates 12\r
+#define kNumPosBitsMax 4\r
+\r
+ CProb IsMatch[kNumStates << kNumPosBitsMax];\r
+ CProb IsRep[kNumStates];\r
+ CProb IsRepG0[kNumStates];\r
+ CProb IsRepG1[kNumStates];\r
+ CProb IsRepG2[kNumStates];\r
+ CProb IsRep0Long[kNumStates << kNumPosBitsMax];\r
+\r
+The decoder uses "state" variable value to select exact variable \r
+from "IsRep", "IsRepG0", "IsRepG1" and "IsRepG2" arrays.\r
+The "state" variable can get the value from 0 to 11.\r
+Initial value for "state" variable is zero:\r
+\r
+ unsigned state = 0;\r
+\r
+The "state" variable is updated after each LITERAL or MATCH with one of the\r
+following functions:\r
+\r
+unsigned UpdateState_Literal(unsigned state)\r
+{\r
+ if (state < 4) return 0;\r
+ else if (state < 10) return state - 3;\r
+ else return state - 6;\r
+}\r
+unsigned UpdateState_Match (unsigned state) { return state < 7 ? 7 : 10; }\r
+unsigned UpdateState_Rep (unsigned state) { return state < 7 ? 8 : 11; }\r
+unsigned UpdateState_ShortRep(unsigned state) { return state < 7 ? 9 : 11; }\r
+\r
+The decoder calculates "state2" variable value to select exact variable from \r
+"IsMatch" and "IsRep0Long" arrays:\r
+\r
+unsigned posState = OutWindow.TotalPos & ((1 << pb) - 1);\r
+unsigned state2 = (state << kNumPosBitsMax) + posState;\r
+\r
+The decoder uses the following code flow scheme to select exact \r
+type of LITERAL or MATCH:\r
+\r
+IsMatch[state2] decode\r
+ 0 - the Literal\r
+ 1 - the Match\r
+ IsRep[state] decode\r
+ 0 - Simple Match\r
+ 1 - Rep Match\r
+ IsRepG0[state] decode\r
+ 0 - the distance is rep0\r
+ IsRep0Long[state2] decode\r
+ 0 - Short Rep Match\r
+ 1 - Rep Match 0\r
+ 1 - \r
+ IsRepG1[state] decode\r
+ 0 - Rep Match 1\r
+ 1 - \r
+ IsRepG2[state] decode\r
+ 0 - Rep Match 2\r
+ 1 - Rep Match 3\r
+\r
+\r
+LITERAL symbol\r
+--------------\r
+If the value "0" was decoded with IsMatch[state2] decoding, we have "LITERAL" type.\r
+\r
+At first the LZMA decoder must check that it doesn't exceed \r
+specified uncompressed size:\r
+\r
+ if (unpackSizeDefined && unpackSize == 0)\r
+ return LZMA_RES_ERROR;\r
+\r
+Then it decodes literal value and puts it to sliding window:\r
+\r
+ DecodeLiteral(state, rep0);\r
+\r
+Then the decoder must update the "state" value and "unpackSize" value;\r
+\r
+ state = UpdateState_Literal(state);\r
+ unpackSize--;\r
+\r
+Then the decoder must go to the begin of main loop to decode next Match or Literal.\r
+\r
+\r
+Simple Match\r
+------------\r
+\r
+If the value "1" was decoded with IsMatch[state2] decoding,\r
+we have the "Simple Match" type.\r
+\r
+The distance history table is updated with the following scheme:\r
+ \r
+ rep3 = rep2;\r
+ rep2 = rep1;\r
+ rep1 = rep0;\r
+\r
+The zero-based length is decoded with "LenDecoder":\r
+\r
+ len = LenDecoder.Decode(&RangeDec, posState);\r
+\r
+The state is update with UpdateState_Match function:\r
+\r
+ state = UpdateState_Match(state);\r
+\r
+and the new "rep0" value is decoded with DecodeDistance:\r
+\r
+ rep0 = DecodeDistance(len);\r
+\r
+That "rep0" will be used as zero-based distance for current match.\r
+\r
+If the value of "rep0" is equal to 0xFFFFFFFF, it means that we have \r
+"End of stream" marker, so we can stop decoding and check finishing \r
+condition in Range Decoder:\r
+\r
+ if (rep0 == 0xFFFFFFFF)\r
+ return RangeDec.IsFinishedOK() ?\r
+ LZMA_RES_FINISHED_WITH_MARKER :\r
+ LZMA_RES_ERROR;\r
+\r
+If uncompressed size is defined, LZMA decoder must check that it doesn't \r
+exceed that specified uncompressed size:\r
+\r
+ if (unpackSizeDefined && unpackSize == 0)\r
+ return LZMA_RES_ERROR;\r
+\r
+Also the decoder must check that "rep0" value is not larger than dictionary size\r
+and is not larger than the number of already decoded bytes:\r
+\r
+ if (rep0 >= dictSize || !OutWindow.CheckDistance(rep0))\r
+ return LZMA_RES_ERROR;\r
+\r
+Then the decoder must copy match bytes as described in \r
+"The match symbols copying" section.\r
+\r
+\r
+Rep Match\r
+---------\r
+\r
+If the LZMA decoder has decoded the value "1" with IsRep[state] variable,\r
+we have "Rep Match" type.\r
+\r
+At first the LZMA decoder must check that it doesn't exceed \r
+specified uncompressed size:\r
+\r
+ if (unpackSizeDefined && unpackSize == 0)\r
+ return LZMA_RES_ERROR;\r
+\r
+Also the decoder must return error, if the LZ window is empty:\r
+\r
+ if (OutWindow.IsEmpty())\r
+ return LZMA_RES_ERROR;\r
+\r
+If the match type is "Rep Match", the decoder uses one of the 4 variables of\r
+distance history table to get the value of distance for current match.\r
+And there are 4 corresponding ways of decoding flow. \r
+\r
+The decoder updates the distance history with the following scheme \r
+depending from type of match:\r
+\r
+- "Rep Match 0" or "Short Rep Match":\r
+ ; LZMA doesn't update the distance history \r
+\r
+- "Rep Match 1":\r
+ UInt32 dist = rep1;\r
+ rep1 = rep0;\r
+ rep0 = dist;\r
+\r
+- "Rep Match 2":\r
+ UInt32 dist = rep2;\r
+ rep2 = rep1;\r
+ rep1 = rep0;\r
+ rep0 = dist;\r
+\r
+- "Rep Match 3":\r
+ UInt32 dist = rep3;\r
+ rep3 = rep2;\r
+ rep2 = rep1;\r
+ rep1 = rep0;\r
+ rep0 = dist;\r
+\r
+Then the decoder decodes exact subtype of "Rep Match" using "IsRepG0", "IsRep0Long",\r
+"IsRepG1", "IsRepG2".\r
+\r
+If the subtype is "Short Rep Match", the decoder updates the state, puts \r
+the one byte from window to current position in window and goes to next \r
+MATCH/LITERAL symbol (the begin of main loop):\r
+\r
+ state = UpdateState_ShortRep(state);\r
+ OutWindow.PutByte(OutWindow.GetByte(rep0 + 1));\r
+ unpackSize--;\r
+ continue;\r
+\r
+In other cases (Rep Match 0/1/2/3), it decodes the zero-based \r
+length of match with "RepLenDecoder" decoder:\r
+\r
+ len = RepLenDecoder.Decode(&RangeDec, posState);\r
+\r
+Then it updates the state:\r
+\r
+ state = UpdateState_Rep(state);\r
+\r
+Then the decoder must copy match bytes as described in \r
+"The Match symbols copying" section.\r
+\r
+\r
+The match symbols copying\r
+-------------------------\r
+\r
+If we have the match (Simple Match or Rep Match 0/1/2/3), the decoder must\r
+copy the sequence of bytes with calculated match distance and match length.\r
+If uncompressed size is defined, LZMA decoder must check that it doesn't \r
+exceed that specified uncompressed size:\r
+\r
+ len += kMatchMinLen;\r
+ bool isError = false;\r
+ if (unpackSizeDefined && unpackSize < len)\r
+ {\r
+ len = (unsigned)unpackSize;\r
+ isError = true;\r
+ }\r
+ OutWindow.CopyMatch(rep0 + 1, len);\r
+ unpackSize -= len;\r
+ if (isError)\r
+ return LZMA_RES_ERROR;\r
+\r
+Then the decoder must go to the begin of main loop to decode next MATCH or LITERAL.\r
+\r
+\r
+\r
+NOTES\r
+-----\r
+\r
+This specification doesn't describe the variant of decoder implementation \r
+that supports partial decoding. Such partial decoding case can require some \r
+changes in "end of stream" condition checks code. Also such code \r
+can use additional status codes, returned by decoder.\r
+\r
+This specification uses C++ code with templates to simplify describing.\r
+The optimized version of LZMA decoder doesn't need templates.\r
+Such optimized version can use just two arrays of CProb variables:\r
+ 1) The dynamic array of CProb variables allocated for the Literal Decoder.\r
+ 2) The one common array that contains all other CProb variables.\r
+\r
+\r
+References: \r
+\r
+1. G. N. N. Martin, Range encoding: an algorithm for removing redundancy \r
+ from a digitized message, Video & Data Recording Conference, \r
+ Southampton, UK, July 24-27, 1979.\r
notaz.gp2x.de / pcsx_rearmed.git / blobdiff