[mirror_edk2.git] / MdeModulePkg / Library / LzmaCustomDecompressLib / Sdk / C / LzmaDec.c

/* LzmaDec.c -- LZMA Decoder\r
2018-07-04 : Igor Pavlov : Public domain */\r
\r
#include "Precomp.h"\r
\r
#ifndef EFIAPI\r
  #include <string.h>\r
#endif\r
\r
/* #include "CpuArch.h" */\r
#include "LzmaDec.h"\r
\r
#define kNumTopBits  24\r
#define kTopValue    ((UInt32)1 << kNumTopBits)\r
\r
#define kNumBitModelTotalBits  11\r
#define kBitModelTotal         (1 << kNumBitModelTotalBits)\r
#define kNumMoveBits           5\r
\r
#define RC_INIT_SIZE  5\r
\r
#define NORMALIZE  if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }\r
\r
#define IF_BIT_0(p)             ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * (UInt32)ttt; if (code < bound)\r
#define UPDATE_0(p)             range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));\r
#define UPDATE_1(p)             range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));\r
#define GET_BIT2(p, i, A0, A1)  IF_BIT_0(p)\\r
  { UPDATE_0(p); i = (i + i); A0; } else \\r
  { UPDATE_1(p); i = (i + i) + 1; A1; }\r
\r
#define TREE_GET_BIT(probs, i)  { GET_BIT2(probs + i, i, ;, ;); }\r
\r
#define REV_BIT(p, i, A0, A1)   IF_BIT_0(p + i)\\r
  { UPDATE_0(p + i); A0; } else \\r
  { UPDATE_1(p + i); A1; }\r
#define REV_BIT_VAR(p, i, m)    REV_BIT(p, i, i += m; m += m, m += m; i += m; )\r
#define REV_BIT_CONST(p, i, m)  REV_BIT(p, i, i += m;       , i += m * 2; )\r
#define REV_BIT_LAST(p, i, m)   REV_BIT(p, i, i -= m        , ; )\r
\r
#define TREE_DECODE(probs, limit, i) \\r
  { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }\r
\r
/* #define _LZMA_SIZE_OPT */\r
\r
#ifdef _LZMA_SIZE_OPT\r
#define TREE_6_DECODE(probs, i)  TREE_DECODE(probs, (1 << 6), i)\r
#else\r
#define TREE_6_DECODE(probs, i) \\r
  { i = 1; \\r
  TREE_GET_BIT(probs, i); \\r
  TREE_GET_BIT(probs, i); \\r
  TREE_GET_BIT(probs, i); \\r
  TREE_GET_BIT(probs, i); \\r
  TREE_GET_BIT(probs, i); \\r
  TREE_GET_BIT(probs, i); \\r
  i -= 0x40; }\r
#endif\r
\r
#define NORMAL_LITER_DEC  TREE_GET_BIT(prob, symbol)\r
#define MATCHED_LITER_DEC \\r
  matchByte += matchByte; \\r
  bit = offs; \\r
  offs &= matchByte; \\r
  probLit = prob + (offs + bit + symbol); \\r
  GET_BIT2(probLit, symbol, offs ^= bit; , ;)\r
\r
#define NORMALIZE_CHECK  if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); }\r
\r
#define IF_BIT_0_CHECK(p)  ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * (UInt32)ttt; if (code < bound)\r
#define UPDATE_0_CHECK  range = bound;\r
#define UPDATE_1_CHECK  range -= bound; code -= bound;\r
#define GET_BIT2_CHECK(p, i, A0, A1)  IF_BIT_0_CHECK(p)\\r
  { UPDATE_0_CHECK; i = (i + i); A0; } else \\r
  { UPDATE_1_CHECK; i = (i + i) + 1; A1; }\r
#define GET_BIT_CHECK(p, i)           GET_BIT2_CHECK(p, i, ; , ;)\r
#define TREE_DECODE_CHECK(probs, limit, i) \\r
  { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; }\r
\r
#define REV_BIT_CHECK(p, i, m)  IF_BIT_0_CHECK(p + i)\\r
  { UPDATE_0_CHECK; i += m; m += m; } else \\r
  { UPDATE_1_CHECK; m += m; i += m; }\r
\r
#define kNumPosBitsMax    4\r
#define kNumPosStatesMax  (1 << kNumPosBitsMax)\r
\r
#define kLenNumLowBits      3\r
#define kLenNumLowSymbols   (1 << kLenNumLowBits)\r
#define kLenNumHighBits     8\r
#define kLenNumHighSymbols  (1 << kLenNumHighBits)\r
\r
#define LenLow        0\r
#define LenHigh       (LenLow + 2 * (kNumPosStatesMax << kLenNumLowBits))\r
#define kNumLenProbs  (LenHigh + kLenNumHighSymbols)\r
\r
#define LenChoice   LenLow\r
#define LenChoice2  (LenLow + (1 << kLenNumLowBits))\r
\r
#define kNumStates     12\r
#define kNumStates2    16\r
#define kNumLitStates  7\r
\r
#define kStartPosModelIndex  4\r
#define kEndPosModelIndex    14\r
#define kNumFullDistances    (1 << (kEndPosModelIndex >> 1))\r
\r
#define kNumPosSlotBits     6\r
#define kNumLenToPosStates  4\r
\r
#define kNumAlignBits    4\r
#define kAlignTableSize  (1 << kNumAlignBits)\r
\r
#define kMatchMinLen        2\r
#define kMatchSpecLenStart  (kMatchMinLen + kLenNumLowSymbols * 2 + kLenNumHighSymbols)\r
\r
/* External ASM code needs same CLzmaProb array layout. So don't change it. */\r
\r
/* (probs_1664) is faster and better for code size at some platforms */\r
\r
/*\r
#ifdef MY_CPU_X86_OR_AMD64\r
*/\r
#define kStartOffset  1664\r
#define GET_PROBS     p->probs_1664\r
\r
/*\r
#define GET_PROBS p->probs + kStartOffset\r
#else\r
#define kStartOffset 0\r
#define GET_PROBS p->probs\r
#endif\r
*/\r
\r
#define SpecPos         (-kStartOffset)\r
#define IsRep0Long      (SpecPos + kNumFullDistances)\r
#define RepLenCoder     (IsRep0Long + (kNumStates2 << kNumPosBitsMax))\r
#define LenCoder        (RepLenCoder + kNumLenProbs)\r
#define IsMatch         (LenCoder + kNumLenProbs)\r
#define Align           (IsMatch + (kNumStates2 << kNumPosBitsMax))\r
#define IsRep           (Align + kAlignTableSize)\r
#define IsRepG0         (IsRep + kNumStates)\r
#define IsRepG1         (IsRepG0 + kNumStates)\r
#define IsRepG2         (IsRepG1 + kNumStates)\r
#define PosSlot         (IsRepG2 + kNumStates)\r
#define Literal         (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))\r
#define NUM_BASE_PROBS  (Literal + kStartOffset)\r
\r
#if Align != 0 && kStartOffset != 0\r
  #error Stop_Compiling_Bad_LZMA_kAlign\r
#endif\r
\r
#if NUM_BASE_PROBS != 1984\r
  #error Stop_Compiling_Bad_LZMA_PROBS\r
#endif\r
\r
#define LZMA_LIT_SIZE  0x300\r
\r
#define LzmaProps_GetNumProbs(p)  (NUM_BASE_PROBS + ((UInt32)LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))\r
\r
#define CALC_POS_STATE(processedPos, pbMask)  (((processedPos) & (pbMask)) << 4)\r
#define COMBINED_PS_STATE  (posState + state)\r
#define GET_LEN_STATE      (posState)\r
\r
#define LZMA_DIC_MIN  (1 << 12)\r
\r
/*\r
p->remainLen : shows status of LZMA decoder:\r
    < kMatchSpecLenStart : normal remain\r
    = kMatchSpecLenStart : finished\r
    = kMatchSpecLenStart + 1 : need init range coder\r
    = kMatchSpecLenStart + 2 : need init range coder and state\r
*/\r
\r
/* ---------- LZMA_DECODE_REAL ---------- */\r
\r
/*\r
LzmaDec_DecodeReal_3() can be implemented in external ASM file.\r
3 - is the code compatibility version of that function for check at link time.\r
*/\r
\r
#define LZMA_DECODE_REAL  LzmaDec_DecodeReal_3\r
\r
/*\r
LZMA_DECODE_REAL()\r
In:\r
  RangeCoder is normalized\r
  if (p->dicPos == limit)\r
  {\r
    LzmaDec_TryDummy() was called before to exclude LITERAL and MATCH-REP cases.\r
    So first symbol can be only MATCH-NON-REP. And if that MATCH-NON-REP symbol\r
    is not END_OF_PAYALOAD_MARKER, then function returns error code.\r
  }\r
\r
Processing:\r
  first LZMA symbol will be decoded in any case\r
  All checks for limits are at the end of main loop,\r
  It will decode new LZMA-symbols while (p->buf < bufLimit && dicPos < limit),\r
  RangeCoder is still without last normalization when (p->buf < bufLimit) is being checked.\r
\r
Out:\r
  RangeCoder is normalized\r
  Result:\r
    SZ_OK - OK\r
    SZ_ERROR_DATA - Error\r
  p->remainLen:\r
    < kMatchSpecLenStart : normal remain\r
    = kMatchSpecLenStart : finished\r
*/\r
\r
#ifdef _LZMA_DEC_OPT\r
\r
int MY_FAST_CALL\r
LZMA_DECODE_REAL (\r
  CLzmaDec    *p,\r
  SizeT       limit,\r
  const Byte  *bufLimit\r
  );\r
\r
#else\r
\r
static\r
int MY_FAST_CALL\r
LZMA_DECODE_REAL (\r
  CLzmaDec    *p,\r
  SizeT       limit,\r
  const Byte  *bufLimit\r
  )\r
{\r
  CLzmaProb  *probs = GET_PROBS;\r
  unsigned   state = (unsigned)p->state;\r
  UInt32     rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];\r
  unsigned   pbMask = ((unsigned)1 << (p->prop.pb)) - 1;\r
  unsigned   lc     = p->prop.lc;\r
  unsigned   lpMask = ((unsigned)0x100 << p->prop.lp) - ((unsigned)0x100 >> lc);\r
\r
  Byte   *dic       = p->dic;\r
  SizeT  dicBufSize = p->dicBufSize;\r
  SizeT  dicPos     = p->dicPos;\r
\r
  UInt32    processedPos = p->processedPos;\r
  UInt32    checkDicSize = p->checkDicSize;\r
  unsigned  len          = 0;\r
\r
  const Byte  *buf  = p->buf;\r
  UInt32      range = p->range;\r
  UInt32      code  = p->code;\r
\r
  do {\r
    CLzmaProb  *prob;\r
    UInt32     bound;\r
    unsigned   ttt;\r
    unsigned   posState = CALC_POS_STATE (processedPos, pbMask);\r
\r
    prob = probs + IsMatch + COMBINED_PS_STATE;\r
    IF_BIT_0 (prob) {\r
      unsigned  symbol;\r
\r
      UPDATE_0 (prob);\r
      prob = probs + Literal;\r
      if ((processedPos != 0) || (checkDicSize != 0)) {\r
        prob += (UInt32)3 * ((((processedPos << 8) + dic[(dicPos == 0 ? dicBufSize : dicPos) - 1]) & lpMask) << lc);\r
      }\r
\r
      processedPos++;\r
\r
      if (state < kNumLitStates) {\r
        state -= (state < 4) ? state : 3;\r
        symbol = 1;\r
 #ifdef _LZMA_SIZE_OPT\r
        do {\r
          NORMAL_LITER_DEC\r
        } while (symbol < 0x100);\r
\r
 #else\r
        NORMAL_LITER_DEC\r
        NORMAL_LITER_DEC\r
        NORMAL_LITER_DEC\r
        NORMAL_LITER_DEC\r
        NORMAL_LITER_DEC\r
        NORMAL_LITER_DEC\r
        NORMAL_LITER_DEC\r
          NORMAL_LITER_DEC\r
 #endif\r
      } else {\r
        unsigned  matchByte = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];\r
        unsigned  offs      = 0x100;\r
        state -= (state < 10) ? 3 : 6;\r
        symbol = 1;\r
 #ifdef _LZMA_SIZE_OPT\r
        do {\r
          unsigned   bit;\r
          CLzmaProb  *probLit;\r
          MATCHED_LITER_DEC\r
        } while (symbol < 0x100);\r
\r
 #else\r
        {\r
          unsigned   bit;\r
          CLzmaProb  *probLit;\r
          MATCHED_LITER_DEC\r
          MATCHED_LITER_DEC\r
          MATCHED_LITER_DEC\r
          MATCHED_LITER_DEC\r
          MATCHED_LITER_DEC\r
          MATCHED_LITER_DEC\r
          MATCHED_LITER_DEC\r
            MATCHED_LITER_DEC\r
        }\r
 #endif\r
      }\r
\r
      dic[dicPos++] = (Byte)symbol;\r
      continue;\r
    }\r
\r
    {\r
      UPDATE_1 (prob);\r
      prob = probs + IsRep + state;\r
      IF_BIT_0 (prob) {\r
        UPDATE_0 (prob);\r
        state += kNumStates;\r
        prob   = probs + LenCoder;\r
      } else {\r
        UPDATE_1 (prob);\r
\r
        /*\r
        // that case was checked before with kBadRepCode\r
        if (checkDicSize == 0 && processedPos == 0)\r
          return SZ_ERROR_DATA;\r
        */\r
        prob = probs + IsRepG0 + state;\r
        IF_BIT_0 (prob) {\r
          UPDATE_0 (prob);\r
          prob = probs + IsRep0Long + COMBINED_PS_STATE;\r
          IF_BIT_0 (prob) {\r
            UPDATE_0 (prob);\r
            dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];\r
            dicPos++;\r
            processedPos++;\r
            state = state < kNumLitStates ? 9 : 11;\r
            continue;\r
          }\r
          UPDATE_1 (prob);\r
        } else {\r
          UInt32  distance;\r
          UPDATE_1 (prob);\r
          prob = probs + IsRepG1 + state;\r
          IF_BIT_0 (prob) {\r
            UPDATE_0 (prob);\r
            distance = rep1;\r
          } else {\r
            UPDATE_1 (prob);\r
            prob = probs + IsRepG2 + state;\r
            IF_BIT_0 (prob) {\r
              UPDATE_0 (prob);\r
              distance = rep2;\r
            } else {\r
              UPDATE_1 (prob);\r
              distance = rep3;\r
              rep3     = rep2;\r
            }\r
            rep2 = rep1;\r
          }\r
          rep1 = rep0;\r
          rep0 = distance;\r
        }\r
        state = state < kNumLitStates ? 8 : 11;\r
        prob  = probs + RepLenCoder;\r
      }\r
\r
 #ifdef _LZMA_SIZE_OPT\r
      {\r
        unsigned   lim, offset;\r
        CLzmaProb  *probLen = prob + LenChoice;\r
        IF_BIT_0 (probLen) {\r
          UPDATE_0 (probLen);\r
          probLen = prob + LenLow + GET_LEN_STATE;\r
          offset  = 0;\r
          lim     = (1 << kLenNumLowBits);\r
        } else {\r
          UPDATE_1 (probLen);\r
          probLen = prob + LenChoice2;\r
          IF_BIT_0 (probLen) {\r
            UPDATE_0 (probLen);\r
            probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits);\r
            offset  = kLenNumLowSymbols;\r
            lim     = (1 << kLenNumLowBits);\r
          } else {\r
            UPDATE_1 (probLen);\r
            probLen = prob + LenHigh;\r
            offset  = kLenNumLowSymbols * 2;\r
            lim     = (1 << kLenNumHighBits);\r
          }\r
        }\r
        TREE_DECODE (probLen, lim, len);\r
        len += offset;\r
      }\r
 #else\r
      {\r
        CLzmaProb  *probLen = prob + LenChoice;\r
        IF_BIT_0 (probLen) {\r
          UPDATE_0 (probLen);\r
          probLen = prob + LenLow + GET_LEN_STATE;\r
          len     = 1;\r
          TREE_GET_BIT (probLen, len);\r
          TREE_GET_BIT (probLen, len);\r
          TREE_GET_BIT (probLen, len);\r
          len -= 8;\r
        } else {\r
          UPDATE_1 (probLen);\r
          probLen = prob + LenChoice2;\r
          IF_BIT_0 (probLen) {\r
            UPDATE_0 (probLen);\r
            probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits);\r
            len     = 1;\r
            TREE_GET_BIT (probLen, len);\r
            TREE_GET_BIT (probLen, len);\r
            TREE_GET_BIT (probLen, len);\r
          } else {\r
            UPDATE_1 (probLen);\r
            probLen = prob + LenHigh;\r
            TREE_DECODE (probLen, (1 << kLenNumHighBits), len);\r
            len += kLenNumLowSymbols * 2;\r
          }\r
        }\r
      }\r
 #endif\r
\r
      if (state >= kNumStates) {\r
        UInt32  distance;\r
        prob = probs + PosSlot +\r
               ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);\r
        TREE_6_DECODE (prob, distance);\r
        if (distance >= kStartPosModelIndex) {\r
          unsigned  posSlot       = (unsigned)distance;\r
          unsigned  numDirectBits = (unsigned)(((distance >> 1) - 1));\r
          distance = (2 | (distance & 1));\r
          if (posSlot < kEndPosModelIndex) {\r
            distance <<= numDirectBits;\r
            prob       = probs + SpecPos;\r
            {\r
              UInt32  m = 1;\r
              distance++;\r
              do {\r
                REV_BIT_VAR (prob, distance, m);\r
              } while (--numDirectBits);\r
\r
              distance -= m;\r
            }\r
          } else {\r
            numDirectBits -= kNumAlignBits;\r
            do {\r
              NORMALIZE\r
                range >>= 1;\r
\r
              {\r
                UInt32  t;\r
                code    -= range;\r
                t        = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */\r
                distance = (distance << 1) + (t + 1);\r
                code    += range & t;\r
              }\r
\r
              /*\r
              distance <<= 1;\r
              if (code >= range)\r
              {\r
                code -= range;\r
                distance |= 1;\r
              }\r
              */\r
            } while (--numDirectBits);\r
\r
            prob       = probs + Align;\r
            distance <<= kNumAlignBits;\r
            {\r
              unsigned  i = 1;\r
              REV_BIT_CONST (prob, i, 1);\r
              REV_BIT_CONST (prob, i, 2);\r
              REV_BIT_CONST (prob, i, 4);\r
              REV_BIT_LAST (prob, i, 8);\r
              distance |= i;\r
            }\r
            if (distance == (UInt32)0xFFFFFFFF) {\r
              len    = kMatchSpecLenStart;\r
              state -= kNumStates;\r
              break;\r
            }\r
          }\r
        }\r
\r
        rep3  = rep2;\r
        rep2  = rep1;\r
        rep1  = rep0;\r
        rep0  = distance + 1;\r
        state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;\r
        if (distance >= ((checkDicSize == 0) ? processedPos : checkDicSize)) {\r
          p->dicPos = dicPos;\r
          return SZ_ERROR_DATA;\r
        }\r
      }\r
\r
      len += kMatchMinLen;\r
\r
      {\r
        SizeT     rem;\r
        unsigned  curLen;\r
        SizeT     pos;\r
\r
        if ((rem = limit - dicPos) == 0) {\r
          p->dicPos = dicPos;\r
          return SZ_ERROR_DATA;\r
        }\r
\r
        curLen = ((rem < len) ? (unsigned)rem : len);\r
        pos    = dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0);\r
\r
        processedPos += (UInt32)curLen;\r
\r
        len -= curLen;\r
        if (curLen <= dicBufSize - pos) {\r
          Byte        *dest = dic + dicPos;\r
          ptrdiff_t   src   = (ptrdiff_t)pos - (ptrdiff_t)dicPos;\r
          const Byte  *lim  = dest + curLen;\r
          dicPos += (SizeT)curLen;\r
          do {\r
            *(dest) = (Byte)*(dest + src);\r
          } while (++dest != lim);\r
        } else {\r
          do {\r
            dic[dicPos++] = dic[pos];\r
            if (++pos == dicBufSize) {\r
              pos = 0;\r
            }\r
          } while (--curLen != 0);\r
        }\r
      }\r
    }\r
  } while (dicPos < limit && buf < bufLimit);\r
\r
  NORMALIZE;\r
\r
  p->buf          = buf;\r
  p->range        = range;\r
  p->code         = code;\r
  p->remainLen    = (UInt32)len;\r
  p->dicPos       = dicPos;\r
  p->processedPos = processedPos;\r
  p->reps[0]      = rep0;\r
  p->reps[1]      = rep1;\r
  p->reps[2]      = rep2;\r
  p->reps[3]      = rep3;\r
  p->state        = (UInt32)state;\r
\r
  return SZ_OK;\r
}\r
\r
#endif\r
\r
static void MY_FAST_CALL\r
LzmaDec_WriteRem (\r
  CLzmaDec  *p,\r
  SizeT     limit\r
  )\r
{\r
  if ((p->remainLen != 0) && (p->remainLen < kMatchSpecLenStart)) {\r
    Byte      *dic       = p->dic;\r
    SizeT     dicPos     = p->dicPos;\r
    SizeT     dicBufSize = p->dicBufSize;\r
    unsigned  len        = (unsigned)p->remainLen;\r
    SizeT     rep0       = p->reps[0]; /* we use SizeT to avoid the BUG of VC14 for AMD64 */\r
    SizeT     rem        = limit - dicPos;\r
    if (rem < len) {\r
      len = (unsigned)(rem);\r
    }\r
\r
    if ((p->checkDicSize == 0) && (p->prop.dicSize - p->processedPos <= len)) {\r
      p->checkDicSize = p->prop.dicSize;\r
    }\r
\r
    p->processedPos += (UInt32)len;\r
    p->remainLen    -= (UInt32)len;\r
    while (len != 0) {\r
      len--;\r
      dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];\r
      dicPos++;\r
    }\r
\r
    p->dicPos = dicPos;\r
  }\r
}\r
\r
#define kRange0      0xFFFFFFFF\r
#define kBound0      ((kRange0 >> kNumBitModelTotalBits) << (kNumBitModelTotalBits - 1))\r
#define kBadRepCode  (kBound0 + (((kRange0 - kBound0) >> kNumBitModelTotalBits) << (kNumBitModelTotalBits - 1)))\r
#if kBadRepCode != (0xC0000000 - 0x400)\r
  #error Stop_Compiling_Bad_LZMA_Check\r
#endif\r
\r
static int MY_FAST_CALL\r
LzmaDec_DecodeReal2 (\r
  CLzmaDec    *p,\r
  SizeT       limit,\r
  const Byte  *bufLimit\r
  )\r
{\r
  do {\r
    SizeT  limit2 = limit;\r
    if (p->checkDicSize == 0) {\r
      UInt32  rem = p->prop.dicSize - p->processedPos;\r
      if (limit - p->dicPos > rem) {\r
        limit2 = p->dicPos + rem;\r
      }\r
\r
      if (p->processedPos == 0) {\r
        if (p->code >= kBadRepCode) {\r
          return SZ_ERROR_DATA;\r
        }\r
      }\r
    }\r
\r
    RINOK (LZMA_DECODE_REAL (p, limit2, bufLimit));\r
\r
    if ((p->checkDicSize == 0) && (p->processedPos >= p->prop.dicSize)) {\r
      p->checkDicSize = p->prop.dicSize;\r
    }\r
\r
    LzmaDec_WriteRem (p, limit);\r
  } while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);\r
\r
  return 0;\r
}\r
\r
typedef enum {\r
  DUMMY_ERROR, /* unexpected end of input stream */\r
  DUMMY_LIT,\r
  DUMMY_MATCH,\r
  DUMMY_REP\r
} ELzmaDummy;\r
\r
static ELzmaDummy\r
LzmaDec_TryDummy (\r
  const CLzmaDec  *p,\r
  const Byte      *buf,\r
  SizeT           inSize\r
  )\r
{\r
  UInt32           range     = p->range;\r
  UInt32           code      = p->code;\r
  const Byte       *bufLimit = buf + inSize;\r
  const CLzmaProb  *probs    = GET_PROBS;\r
  unsigned         state     = (unsigned)p->state;\r
  ELzmaDummy       res;\r
\r
  {\r
    const CLzmaProb  *prob;\r
    UInt32           bound;\r
    unsigned         ttt;\r
    unsigned         posState = CALC_POS_STATE (p->processedPos, (1 << p->prop.pb) - 1);\r
\r
    prob = probs + IsMatch + COMBINED_PS_STATE;\r
    IF_BIT_0_CHECK (prob) {\r
      UPDATE_0_CHECK\r
\r
      /* if (bufLimit - buf >= 7) return DUMMY_LIT; */\r
\r
        prob = probs + Literal;\r
\r
      if ((p->checkDicSize != 0) || (p->processedPos != 0)) {\r
        prob += ((UInt32)LZMA_LIT_SIZE *\r
                 ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +\r
                  (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));\r
      }\r
\r
      if (state < kNumLitStates) {\r
        unsigned  symbol = 1;\r
        do {\r
          GET_BIT_CHECK (prob + symbol, symbol)\r
        } while (symbol < 0x100);\r
      } else {\r
        unsigned  matchByte = p->dic[p->dicPos - p->reps[0] +\r
                                     (p->dicPos < p->reps[0] ? p->dicBufSize : 0)];\r
        unsigned  offs   = 0x100;\r
        unsigned  symbol = 1;\r
        do {\r
          unsigned         bit;\r
          const CLzmaProb  *probLit;\r
          matchByte += matchByte;\r
          bit        = offs;\r
          offs      &= matchByte;\r
          probLit    = prob + (offs + bit + symbol);\r
          GET_BIT2_CHECK (\r
            probLit,\r
            symbol,\r
            offs ^= bit;\r
                         ,\r
            ;\r
            )\r
        } while (symbol < 0x100);\r
      }\r
\r
      res = DUMMY_LIT;\r
    } else {\r
      unsigned  len;\r
      UPDATE_1_CHECK;\r
\r
      prob = probs + IsRep + state;\r
      IF_BIT_0_CHECK (prob) {\r
        UPDATE_0_CHECK;\r
        state = 0;\r
        prob  = probs + LenCoder;\r
        res   = DUMMY_MATCH;\r
      } else {\r
        UPDATE_1_CHECK;\r
        res  = DUMMY_REP;\r
        prob = probs + IsRepG0 + state;\r
        IF_BIT_0_CHECK (prob) {\r
          UPDATE_0_CHECK;\r
          prob = probs + IsRep0Long + COMBINED_PS_STATE;\r
          IF_BIT_0_CHECK (prob) {\r
            UPDATE_0_CHECK;\r
            NORMALIZE_CHECK;\r
            return DUMMY_REP;\r
          } else {\r
            UPDATE_1_CHECK;\r
          }\r
        } else {\r
          UPDATE_1_CHECK;\r
          prob = probs + IsRepG1 + state;\r
          IF_BIT_0_CHECK (prob) {\r
            UPDATE_0_CHECK;\r
          } else {\r
            UPDATE_1_CHECK;\r
            prob = probs + IsRepG2 + state;\r
            IF_BIT_0_CHECK (prob) {\r
              UPDATE_0_CHECK;\r
            } else {\r
              UPDATE_1_CHECK;\r
            }\r
          }\r
        }\r
        state = kNumStates;\r
        prob  = probs + RepLenCoder;\r
      }\r
      {\r
        unsigned         limit, offset;\r
        const CLzmaProb  *probLen = prob + LenChoice;\r
        IF_BIT_0_CHECK (probLen) {\r
          UPDATE_0_CHECK;\r
          probLen = prob + LenLow + GET_LEN_STATE;\r
          offset  = 0;\r
          limit   = 1 << kLenNumLowBits;\r
        } else {\r
          UPDATE_1_CHECK;\r
          probLen = prob + LenChoice2;\r
          IF_BIT_0_CHECK (probLen) {\r
            UPDATE_0_CHECK;\r
            probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits);\r
            offset  = kLenNumLowSymbols;\r
            limit   = 1 << kLenNumLowBits;\r
          } else {\r
            UPDATE_1_CHECK;\r
            probLen = prob + LenHigh;\r
            offset  = kLenNumLowSymbols * 2;\r
            limit   = 1 << kLenNumHighBits;\r
          }\r
        }\r
        TREE_DECODE_CHECK (probLen, limit, len);\r
        len += offset;\r
      }\r
\r
      if (state < 4) {\r
        unsigned  posSlot;\r
        prob = probs + PosSlot +\r
               ((len < kNumLenToPosStates - 1 ? len : kNumLenToPosStates - 1) <<\r
                kNumPosSlotBits);\r
        TREE_DECODE_CHECK (prob, 1 << kNumPosSlotBits, posSlot);\r
        if (posSlot >= kStartPosModelIndex) {\r
          unsigned  numDirectBits = ((posSlot >> 1) - 1);\r
\r
          /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */\r
\r
          if (posSlot < kEndPosModelIndex) {\r
            prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits);\r
          } else {\r
            numDirectBits -= kNumAlignBits;\r
            do {\r
              NORMALIZE_CHECK\r
                range >>= 1;\r
              code -= range & (((code - range) >> 31) - 1);\r
              /* if (code >= range) code -= range; */\r
            } while (--numDirectBits);\r
\r
            prob          = probs + Align;\r
            numDirectBits = kNumAlignBits;\r
          }\r
\r
          {\r
            unsigned  i = 1;\r
            unsigned  m = 1;\r
            do {\r
              REV_BIT_CHECK (prob, i, m);\r
            } while (--numDirectBits);\r
          }\r
        }\r
      }\r
    }\r
  }\r
\r
  NORMALIZE_CHECK;\r
  return res;\r
}\r
\r
void\r
LzmaDec_InitDicAndState (\r
  CLzmaDec  *p,\r
  BoolInt   initDic,\r
  BoolInt   initState\r
  )\r
{\r
  p->remainLen   = kMatchSpecLenStart + 1;\r
  p->tempBufSize = 0;\r
\r
  if (initDic) {\r
    p->processedPos = 0;\r
    p->checkDicSize = 0;\r
    p->remainLen    = kMatchSpecLenStart + 2;\r
  }\r
\r
  if (initState) {\r
    p->remainLen = kMatchSpecLenStart + 2;\r
  }\r
}\r
\r
void\r
LzmaDec_Init (\r
  CLzmaDec  *p\r
  )\r
{\r
  p->dicPos = 0;\r
  LzmaDec_InitDicAndState (p, True, True);\r
}\r
\r
SRes\r
LzmaDec_DecodeToDic (\r
  CLzmaDec         *p,\r
  SizeT            dicLimit,\r
  const Byte       *src,\r
  SizeT            *srcLen,\r
  ELzmaFinishMode  finishMode,\r
  ELzmaStatus      *status\r
  )\r
{\r
  SizeT  inSize = *srcLen;\r
\r
  (*srcLen) = 0;\r
\r
  *status = LZMA_STATUS_NOT_SPECIFIED;\r
\r
  if (p->remainLen > kMatchSpecLenStart) {\r
    for ( ; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--) {\r
      p->tempBuf[p->tempBufSize++] = *src++;\r
    }\r
\r
    if ((p->tempBufSize != 0) && (p->tempBuf[0] != 0)) {\r
      return SZ_ERROR_DATA;\r
    }\r
\r
    if (p->tempBufSize < RC_INIT_SIZE) {\r
      *status = LZMA_STATUS_NEEDS_MORE_INPUT;\r
      return SZ_OK;\r
    }\r
\r
    p->code =\r
      ((UInt32)p->tempBuf[1] << 24)\r
      | ((UInt32)p->tempBuf[2] << 16)\r
      | ((UInt32)p->tempBuf[3] << 8)\r
      | ((UInt32)p->tempBuf[4]);\r
    p->range       = 0xFFFFFFFF;\r
    p->tempBufSize = 0;\r
\r
    if (p->remainLen > kMatchSpecLenStart + 1) {\r
      SizeT      numProbs = LzmaProps_GetNumProbs (&p->prop);\r
      SizeT      i;\r
      CLzmaProb  *probs = p->probs;\r
      for (i = 0; i < numProbs; i++) {\r
        probs[i] = kBitModelTotal >> 1;\r
      }\r
\r
      p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;\r
      p->state   = 0;\r
    }\r
\r
    p->remainLen = 0;\r
  }\r
\r
  LzmaDec_WriteRem (p, dicLimit);\r
\r
  while (p->remainLen != kMatchSpecLenStart) {\r
    int  checkEndMarkNow = 0;\r
\r
    if (p->dicPos >= dicLimit) {\r
      if ((p->remainLen == 0) && (p->code == 0)) {\r
        *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;\r
        return SZ_OK;\r
      }\r
\r
      if (finishMode == LZMA_FINISH_ANY) {\r
        *status = LZMA_STATUS_NOT_FINISHED;\r
        return SZ_OK;\r
      }\r
\r
      if (p->remainLen != 0) {\r
        *status = LZMA_STATUS_NOT_FINISHED;\r
        return SZ_ERROR_DATA;\r
      }\r
\r
      checkEndMarkNow = 1;\r
    }\r
\r
    if (p->tempBufSize == 0) {\r
      SizeT       processed;\r
      const Byte  *bufLimit;\r
      if ((inSize < LZMA_REQUIRED_INPUT_MAX) || checkEndMarkNow) {\r
        int  dummyRes = LzmaDec_TryDummy (p, src, inSize);\r
        if (dummyRes == DUMMY_ERROR) {\r
          memcpy (p->tempBuf, src, inSize);\r
          p->tempBufSize = (unsigned)inSize;\r
          (*srcLen)     += inSize;\r
          *status        = LZMA_STATUS_NEEDS_MORE_INPUT;\r
          return SZ_OK;\r
        }\r
\r
        if (checkEndMarkNow && (dummyRes != DUMMY_MATCH)) {\r
          *status = LZMA_STATUS_NOT_FINISHED;\r
          return SZ_ERROR_DATA;\r
        }\r
\r
        bufLimit = src;\r
      } else {\r
        bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;\r
      }\r
\r
      p->buf = src;\r
      if (LzmaDec_DecodeReal2 (p, dicLimit, bufLimit) != 0) {\r
        return SZ_ERROR_DATA;\r
      }\r
\r
      processed  = (SizeT)(p->buf - src);\r
      (*srcLen) += processed;\r
      src       += processed;\r
      inSize    -= processed;\r
    } else {\r
      unsigned  rem = p->tempBufSize, lookAhead = 0;\r
      while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize) {\r
        p->tempBuf[rem++] = src[lookAhead++];\r
      }\r
\r
      p->tempBufSize = rem;\r
      if ((rem < LZMA_REQUIRED_INPUT_MAX) || checkEndMarkNow) {\r
        int  dummyRes = LzmaDec_TryDummy (p, p->tempBuf, (SizeT)rem);\r
        if (dummyRes == DUMMY_ERROR) {\r
          (*srcLen) += (SizeT)lookAhead;\r
          *status    = LZMA_STATUS_NEEDS_MORE_INPUT;\r
          return SZ_OK;\r
        }\r
\r
        if (checkEndMarkNow && (dummyRes != DUMMY_MATCH)) {\r
          *status = LZMA_STATUS_NOT_FINISHED;\r
          return SZ_ERROR_DATA;\r
        }\r
      }\r
\r
      p->buf = p->tempBuf;\r
      if (LzmaDec_DecodeReal2 (p, dicLimit, p->buf) != 0) {\r
        return SZ_ERROR_DATA;\r
      }\r
\r
      {\r
        unsigned  kkk = (unsigned)(p->buf - p->tempBuf);\r
        if (rem < kkk) {\r
          return SZ_ERROR_FAIL;   /* some internal error */\r
        }\r
\r
        rem -= kkk;\r
        if (lookAhead < rem) {\r
          return SZ_ERROR_FAIL;   /* some internal error */\r
        }\r
\r
        lookAhead -= rem;\r
      }\r
      (*srcLen)     += (SizeT)lookAhead;\r
      src           += lookAhead;\r
      inSize        -= (SizeT)lookAhead;\r
      p->tempBufSize = 0;\r
    }\r
  }\r
\r
  if (p->code != 0) {\r
    return SZ_ERROR_DATA;\r
  }\r
\r
  *status = LZMA_STATUS_FINISHED_WITH_MARK;\r
  return SZ_OK;\r
}\r
\r
SRes\r
LzmaDec_DecodeToBuf (\r
  CLzmaDec         *p,\r
  Byte             *dest,\r
  SizeT            *destLen,\r
  const Byte       *src,\r
  SizeT            *srcLen,\r
  ELzmaFinishMode  finishMode,\r
  ELzmaStatus      *status\r
  )\r
{\r
  SizeT  outSize = *destLen;\r
  SizeT  inSize  = *srcLen;\r
\r
  *srcLen = *destLen = 0;\r
  for ( ; ;) {\r
    SizeT            inSizeCur = inSize, outSizeCur, dicPos;\r
    ELzmaFinishMode  curFinishMode;\r
    SRes             res;\r
    if (p->dicPos == p->dicBufSize) {\r
      p->dicPos = 0;\r
    }\r
\r
    dicPos = p->dicPos;\r
    if (outSize > p->dicBufSize - dicPos) {\r
      outSizeCur    = p->dicBufSize;\r
      curFinishMode = LZMA_FINISH_ANY;\r
    } else {\r
      outSizeCur    = dicPos + outSize;\r
      curFinishMode = finishMode;\r
    }\r
\r
    res        = LzmaDec_DecodeToDic (p, outSizeCur, src, &inSizeCur, curFinishMode, status);\r
    src       += inSizeCur;\r
    inSize    -= inSizeCur;\r
    *srcLen   += inSizeCur;\r
    outSizeCur = p->dicPos - dicPos;\r
    memcpy (dest, p->dic + dicPos, outSizeCur);\r
    dest     += outSizeCur;\r
    outSize  -= outSizeCur;\r
    *destLen += outSizeCur;\r
    if (res != 0) {\r
      return res;\r
    }\r
\r
    if ((outSizeCur == 0) || (outSize == 0)) {\r
      return SZ_OK;\r
    }\r
  }\r
}\r
\r
void\r
LzmaDec_FreeProbs (\r
  CLzmaDec     *p,\r
  ISzAllocPtr  alloc\r
  )\r
{\r
  ISzAlloc_Free (alloc, p->probs);\r
  p->probs = NULL;\r
}\r
\r
static void\r
LzmaDec_FreeDict (\r
  CLzmaDec     *p,\r
  ISzAllocPtr  alloc\r
  )\r
{\r
  ISzAlloc_Free (alloc, p->dic);\r
  p->dic = NULL;\r
}\r
\r
void\r
LzmaDec_Free (\r
  CLzmaDec     *p,\r
  ISzAllocPtr  alloc\r
  )\r
{\r
  LzmaDec_FreeProbs (p, alloc);\r
  LzmaDec_FreeDict (p, alloc);\r
}\r
\r
SRes\r
LzmaProps_Decode (\r
  CLzmaProps  *p,\r
  const Byte  *data,\r
  unsigned    size\r
  )\r
{\r
  UInt32  dicSize;\r
  Byte    d;\r
\r
  if (size < LZMA_PROPS_SIZE) {\r
    return SZ_ERROR_UNSUPPORTED;\r
  } else {\r
    dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);\r
  }\r
\r
  if (dicSize < LZMA_DIC_MIN) {\r
    dicSize = LZMA_DIC_MIN;\r
  }\r
\r
  p->dicSize = dicSize;\r
\r
  d = data[0];\r
  if (d >= (9 * 5 * 5)) {\r
    return SZ_ERROR_UNSUPPORTED;\r
  }\r
\r
  p->lc = (Byte)(d % 9);\r
  d    /= 9;\r
  p->pb = (Byte)(d / 5);\r
  p->lp = (Byte)(d % 5);\r
\r
  return SZ_OK;\r
}\r
\r
static SRes\r
LzmaDec_AllocateProbs2 (\r
  CLzmaDec          *p,\r
  const CLzmaProps  *propNew,\r
  ISzAllocPtr       alloc\r
  )\r
{\r
  UInt32  numProbs = LzmaProps_GetNumProbs (propNew);\r
\r
  if (!p->probs || (numProbs != p->numProbs)) {\r
    LzmaDec_FreeProbs (p, alloc);\r
    p->probs = (CLzmaProb *)ISzAlloc_Alloc (alloc, numProbs * sizeof (CLzmaProb));\r
    if (!p->probs) {\r
      return SZ_ERROR_MEM;\r
    }\r
\r
    p->probs_1664 = p->probs + 1664;\r
    p->numProbs   = numProbs;\r
  }\r
\r
  return SZ_OK;\r
}\r
\r
SRes\r
LzmaDec_AllocateProbs (\r
  CLzmaDec     *p,\r
  const Byte   *props,\r
  unsigned     propsSize,\r
  ISzAllocPtr  alloc\r
  )\r
{\r
  CLzmaProps  propNew;\r
\r
  RINOK (LzmaProps_Decode (&propNew, props, propsSize));\r
  RINOK (LzmaDec_AllocateProbs2 (p, &propNew, alloc));\r
  p->prop = propNew;\r
  return SZ_OK;\r
}\r
\r
SRes\r
LzmaDec_Allocate (\r
  CLzmaDec     *p,\r
  const Byte   *props,\r
  unsigned     propsSize,\r
  ISzAllocPtr  alloc\r
  )\r
{\r
  CLzmaProps  propNew;\r
  SizeT       dicBufSize;\r
\r
  RINOK (LzmaProps_Decode (&propNew, props, propsSize));\r
  RINOK (LzmaDec_AllocateProbs2 (p, &propNew, alloc));\r
\r
  {\r
    UInt32  dictSize = propNew.dicSize;\r
    SizeT   mask     = ((UInt32)1 << 12) - 1;\r
    if (dictSize >= ((UInt32)1 << 30)) {\r
      mask = ((UInt32)1 << 22) - 1;\r
    } else if (dictSize >= ((UInt32)1 << 22)) {\r
      mask = ((UInt32)1 << 20) - 1;\r
    }\r
\r
    dicBufSize = ((SizeT)dictSize + mask) & ~mask;\r
    if (dicBufSize < dictSize) {\r
      dicBufSize = dictSize;\r
    }\r
  }\r
\r
  if (!p->dic || (dicBufSize != p->dicBufSize)) {\r
    LzmaDec_FreeDict (p, alloc);\r
    p->dic = (Byte *)ISzAlloc_Alloc (alloc, dicBufSize);\r
    if (!p->dic) {\r
      LzmaDec_FreeProbs (p, alloc);\r
      return SZ_ERROR_MEM;\r
    }\r
  }\r
\r
  p->dicBufSize = dicBufSize;\r
  p->prop       = propNew;\r
  return SZ_OK;\r
}\r
\r
SRes\r
LzmaDecode (\r
  Byte             *dest,\r
  SizeT            *destLen,\r
  const Byte       *src,\r
  SizeT            *srcLen,\r
  const Byte       *propData,\r
  unsigned         propSize,\r
  ELzmaFinishMode  finishMode,\r
  ELzmaStatus      *status,\r
  ISzAllocPtr      alloc\r
  )\r
{\r
  CLzmaDec  p;\r
  SRes      res;\r
  SizeT     outSize = *destLen, inSize = *srcLen;\r
\r
  *destLen = *srcLen = 0;\r
  *status  = LZMA_STATUS_NOT_SPECIFIED;\r
  if (inSize < RC_INIT_SIZE) {\r
    return SZ_ERROR_INPUT_EOF;\r
  }\r
\r
  LzmaDec_Construct (&p);\r
  RINOK (LzmaDec_AllocateProbs (&p, propData, propSize, alloc));\r
  p.dic        = dest;\r
  p.dicBufSize = outSize;\r
  LzmaDec_Init (&p);\r
  *srcLen  = inSize;\r
  res      = LzmaDec_DecodeToDic (&p, outSize, src, srcLen, finishMode, status);\r
  *destLen = p.dicPos;\r
  if ((res == SZ_OK) && (*status == LZMA_STATUS_NEEDS_MORE_INPUT)) {\r
    res = SZ_ERROR_INPUT_EOF;\r
  }\r
\r
  LzmaDec_FreeProbs (&p, alloc);\r
  return res;\r
}\r