HLE: Merge HLE BIOS improvements from upstream

[pcsx_rearmed.git] / deps / lzma-16.04 / DOC / lzma-specification.txt

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