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

/** @file\r
  LzmaDec.c\r
\r
  Based on LZMA SDK 4.65:\r
    LzmaDec.c -- LZMA Decoder\r
    2008-11-06 : Igor Pavlov : Public domain\r
\r
  Copyright (c) 2009, Intel Corporation. All rights reserved.<BR>\r
  This program and the accompanying materials\r
  are licensed and made available under the terms and conditions of the BSD License\r
  which accompanies this distribution.  The full text of the license may be found at\r
  http://opensource.org/licenses/bsd-license.php\r
\r
  THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
  WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
\r
**/\r
\r
#include "LzmaDec.h"\r
\r
#ifndef EFIAPI\r
\r
#include <string.h>\r
\r
#endif // !EFIAPI\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) * 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
#define GET_BIT(p, i) GET_BIT2(p, i, ; , ;)\r
\r
#define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); }\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 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) * 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
\r
#define kNumPosBitsMax 4\r
#define kNumPosStatesMax (1 << kNumPosBitsMax)\r
\r
#define kLenNumLowBits 3\r
#define kLenNumLowSymbols (1 << kLenNumLowBits)\r
#define kLenNumMidBits 3\r
#define kLenNumMidSymbols (1 << kLenNumMidBits)\r
#define kLenNumHighBits 8\r
#define kLenNumHighSymbols (1 << kLenNumHighBits)\r
\r
#define LenChoice 0\r
#define LenChoice2 (LenChoice + 1)\r
#define LenLow (LenChoice2 + 1)\r
#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))\r
#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))\r
#define kNumLenProbs (LenHigh + kLenNumHighSymbols)\r
\r
\r
#define kNumStates 12\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 + kLenNumMidSymbols + kLenNumHighSymbols)\r
\r
#define IsMatch 0\r
#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))\r
#define IsRepG0 (IsRep + kNumStates)\r
#define IsRepG1 (IsRepG0 + kNumStates)\r
#define IsRepG2 (IsRepG1 + kNumStates)\r
#define IsRep0Long (IsRepG2 + kNumStates)\r
#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))\r
#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))\r
#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)\r
#define LenCoder (Align + kAlignTableSize)\r
#define RepLenCoder (LenCoder + kNumLenProbs)\r
#define Literal (RepLenCoder + kNumLenProbs)\r
\r
#define LZMA_BASE_SIZE 1846\r
#define LZMA_LIT_SIZE 768\r
\r
#define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))\r
\r
#if Literal != LZMA_BASE_SIZE\r
StopCompilingDueBUG\r
#endif\r
\r
static const Byte kLiteralNextStates[kNumStates * 2] =\r
{\r
  0, 0, 0, 0, 1, 2, 3,  4,  5,  6,  4,  5,\r
  7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10\r
};\r
\r
#define LZMA_DIC_MIN (1 << 12)\r
\r
/* First LZMA-symbol is always decoded.\r
And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization\r
Out:\r
  Result:\r
    SZ_OK - OK\r
    SZ_ERROR_DATA - Error\r
  p->remainLen:\r
    < kMatchSpecLenStart : normal remain\r
    = kMatchSpecLenStart : finished\r
    = kMatchSpecLenStart + 1 : Flush marker\r
    = kMatchSpecLenStart + 2 : State Init Marker\r
*/\r
\r
static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit)\r
{\r
  CLzmaProb *probs = p->probs;\r
\r
  unsigned state = 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 lpMask = ((unsigned)1 << (p->prop.lp)) - 1;\r
  unsigned lc = p->prop.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
  {\r
    CLzmaProb *prob;\r
    UInt32 bound;\r
    unsigned ttt;\r
    unsigned posState = processedPos & pbMask;\r
\r
    prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;\r
    IF_BIT_0(prob)\r
    {\r
      unsigned symbol;\r
      UPDATE_0(prob);\r
      prob = probs + Literal;\r
      if (checkDicSize != 0 || processedPos != 0)\r
        prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) +\r
        (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));\r
\r
      if (state < kNumLitStates)\r
      {\r
        symbol = 1;\r
        do { GET_BIT(prob + symbol, symbol) } while (symbol < 0x100);\r
      }\r
      else\r
      {\r
        unsigned matchByte = p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];\r
        unsigned offs = 0x100;\r
        symbol = 1;\r
        do\r
        {\r
          unsigned bit;\r
          CLzmaProb *probLit;\r
          matchByte <<= 1;\r
          bit = (matchByte & offs);\r
          probLit = prob + offs + bit + symbol;\r
          GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)\r
        }\r
        while (symbol < 0x100);\r
      }\r
      dic[dicPos++] = (Byte)symbol;\r
      processedPos++;\r
\r
      state = kLiteralNextStates[state];\r
      /* if (state < 4) state = 0; else if (state < 10) state -= 3; else state -= 6; */\r
      continue;\r
    }\r
    else\r
    {\r
      UPDATE_1(prob);\r
      prob = probs + IsRep + state;\r
      IF_BIT_0(prob)\r
      {\r
        UPDATE_0(prob);\r
        state += kNumStates;\r
        prob = probs + LenCoder;\r
      }\r
      else\r
      {\r
        UPDATE_1(prob);\r
        if (checkDicSize == 0 && processedPos == 0)\r
          return SZ_ERROR_DATA;\r
        prob = probs + IsRepG0 + state;\r
        IF_BIT_0(prob)\r
        {\r
          UPDATE_0(prob);\r
          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;\r
          IF_BIT_0(prob)\r
          {\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
        }\r
        else\r
        {\r
          UInt32 distance;\r
          UPDATE_1(prob);\r
          prob = probs + IsRepG1 + state;\r
          IF_BIT_0(prob)\r
          {\r
            UPDATE_0(prob);\r
            distance = rep1;\r
          }\r
          else\r
          {\r
            UPDATE_1(prob);\r
            prob = probs + IsRepG2 + state;\r
            IF_BIT_0(prob)\r
            {\r
              UPDATE_0(prob);\r
              distance = rep2;\r
            }\r
            else\r
            {\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
        unsigned limit2, offset;\r
        CLzmaProb *probLen = prob + LenChoice;\r
        IF_BIT_0(probLen)\r
        {\r
          UPDATE_0(probLen);\r
          probLen = prob + LenLow + (posState << kLenNumLowBits);\r
          offset = 0;\r
          limit2 = (1 << kLenNumLowBits);\r
        }\r
        else\r
        {\r
          UPDATE_1(probLen);\r
          probLen = prob + LenChoice2;\r
          IF_BIT_0(probLen)\r
          {\r
            UPDATE_0(probLen);\r
            probLen = prob + LenMid + (posState << kLenNumMidBits);\r
            offset = kLenNumLowSymbols;\r
            limit2 = (1 << kLenNumMidBits);\r
          }\r
          else\r
          {\r
            UPDATE_1(probLen);\r
            probLen = prob + LenHigh;\r
            offset = kLenNumLowSymbols + kLenNumMidSymbols;\r
            limit2 = (1 << kLenNumHighBits);\r
          }\r
        }\r
        TREE_DECODE(probLen, limit2, len);\r
        len += offset;\r
      }\r
\r
      if (state >= kNumStates)\r
      {\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
        {\r
          unsigned posSlot = (unsigned)distance;\r
          int numDirectBits = (int)(((distance >> 1) - 1));\r
          distance = (2 | (distance & 1));\r
          if (posSlot < kEndPosModelIndex)\r
          {\r
            distance <<= numDirectBits;\r
            prob = probs + SpecPos + distance - posSlot - 1;\r
            {\r
              UInt32 mask = 1;\r
              unsigned i = 1;\r
              do\r
              {\r
                GET_BIT2(prob + i, i, ; , distance |= mask);\r
                mask <<= 1;\r
              }\r
              while (--numDirectBits != 0);\r
            }\r
          }\r
          else\r
          {\r
            numDirectBits -= kNumAlignBits;\r
            do\r
            {\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
              distance <<= 1;\r
              if (code >= range)\r
              {\r
                code -= range;\r
                distance |= 1;\r
              }\r
              */\r
            }\r
            while (--numDirectBits != 0);\r
            prob = probs + Align;\r
            distance <<= kNumAlignBits;\r
            {\r
              unsigned i = 1;\r
              GET_BIT2(prob + i, i, ; , distance |= 1);\r
              GET_BIT2(prob + i, i, ; , distance |= 2);\r
              GET_BIT2(prob + i, i, ; , distance |= 4);\r
              GET_BIT2(prob + i, i, ; , distance |= 8);\r
            }\r
            if (distance == (UInt32)0xFFFFFFFF)\r
            {\r
              len += kMatchSpecLenStart;\r
              state -= kNumStates;\r
              break;\r
            }\r
          }\r
        }\r
        rep3 = rep2;\r
        rep2 = rep1;\r
        rep1 = rep0;\r
        rep0 = distance + 1;\r
        if (checkDicSize == 0)\r
        {\r
          if (distance >= processedPos)\r
            return SZ_ERROR_DATA;\r
        }\r
        else if (distance >= checkDicSize)\r
          return SZ_ERROR_DATA;\r
        state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;\r
        /* state = kLiteralNextStates[state]; */\r
      }\r
\r
      len += kMatchMinLen;\r
\r
      if (limit == dicPos)\r
        return SZ_ERROR_DATA;\r
      {\r
        SizeT rem = limit - dicPos;\r
        unsigned curLen = ((rem < len) ? (unsigned)rem : len);\r
        SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);\r
\r
        processedPos += curLen;\r
\r
        len -= curLen;\r
        if (pos + curLen <= dicBufSize)\r
        {\r
          Byte *dest = dic + dicPos;\r
          ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;\r
          const Byte *lim = dest + curLen;\r
          dicPos += curLen;\r
          do\r
            *(dest) = (Byte)*(dest + src);\r
          while (++dest != lim);\r
        }\r
        else\r
        {\r
          do\r
          {\r
            dic[dicPos++] = dic[pos];\r
            if (++pos == dicBufSize)\r
              pos = 0;\r
          }\r
          while (--curLen != 0);\r
        }\r
      }\r
    }\r
  }\r
  while (dicPos < limit && buf < bufLimit);\r
  NORMALIZE;\r
  p->buf = buf;\r
  p->range = range;\r
  p->code = code;\r
  p->remainLen = 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 = state;\r
\r
  return SZ_OK;\r
}\r
\r
static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)\r
{\r
  if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)\r
  {\r
    Byte *dic = p->dic;\r
    SizeT dicPos = p->dicPos;\r
    SizeT dicBufSize = p->dicBufSize;\r
    unsigned len = p->remainLen;\r
    UInt32 rep0 = p->reps[0];\r
    if (limit - dicPos < len)\r
      len = (unsigned)(limit - dicPos);\r
\r
    if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)\r
      p->checkDicSize = p->prop.dicSize;\r
\r
    p->processedPos += len;\r
    p->remainLen -= len;\r
    while (len-- != 0)\r
    {\r
      dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];\r
      dicPos++;\r
    }\r
    p->dicPos = dicPos;\r
  }\r
}\r
\r
static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)\r
{\r
  do\r
  {\r
    SizeT limit2 = limit;\r
    if (p->checkDicSize == 0)\r
    {\r
      UInt32 rem = p->prop.dicSize - p->processedPos;\r
      if (limit - p->dicPos > rem)\r
        limit2 = p->dicPos + rem;\r
    }\r
    RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));\r
    if (p->processedPos >= p->prop.dicSize)\r
      p->checkDicSize = p->prop.dicSize;\r
    LzmaDec_WriteRem(p, limit);\r
  }\r
  while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);\r
\r
  if (p->remainLen > kMatchSpecLenStart)\r
  {\r
    p->remainLen = kMatchSpecLenStart;\r
  }\r
  return 0;\r
}\r
\r
typedef enum\r
{\r
  DUMMY_ERROR, /* unexpected end of input stream */\r
  DUMMY_LIT,\r
  DUMMY_MATCH,\r
  DUMMY_REP\r
} ELzmaDummy;\r
\r
static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)\r
{\r
  UInt32 range = p->range;\r
  UInt32 code = p->code;\r
  const Byte *bufLimit = buf + inSize;\r
  CLzmaProb *probs = p->probs;\r
  unsigned state = p->state;\r
  ELzmaDummy res;\r
\r
  {\r
    CLzmaProb *prob;\r
    UInt32 bound;\r
    unsigned ttt;\r
    unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);\r
\r
    prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;\r
    IF_BIT_0_CHECK(prob)\r
    {\r
      UPDATE_0_CHECK\r
\r
      /* if (bufLimit - buf >= 7) return DUMMY_LIT; */\r
\r
      prob = probs + Literal;\r
      if (p->checkDicSize != 0 || p->processedPos != 0)\r
        prob += (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
      if (state < kNumLitStates)\r
      {\r
        unsigned symbol = 1;\r
        do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);\r
      }\r
      else\r
      {\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
        {\r
          unsigned bit;\r
          CLzmaProb *probLit;\r
          matchByte <<= 1;\r
          bit = (matchByte & offs);\r
          probLit = prob + offs + bit + symbol;\r
          GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)\r
        }\r
        while (symbol < 0x100);\r
      }\r
      res = DUMMY_LIT;\r
    }\r
    else\r
    {\r
      unsigned len;\r
      UPDATE_1_CHECK;\r
\r
      prob = probs + IsRep + state;\r
      IF_BIT_0_CHECK(prob)\r
      {\r
        UPDATE_0_CHECK;\r
        state = 0;\r
        prob = probs + LenCoder;\r
        res = DUMMY_MATCH;\r
      }\r
      else\r
      {\r
        UPDATE_1_CHECK;\r
        res = DUMMY_REP;\r
        prob = probs + IsRepG0 + state;\r
        IF_BIT_0_CHECK(prob)\r
        {\r
          UPDATE_0_CHECK;\r
          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;\r
          IF_BIT_0_CHECK(prob)\r
          {\r
            UPDATE_0_CHECK;\r
            NORMALIZE_CHECK;\r
            return DUMMY_REP;\r
          }\r
          else\r
          {\r
            UPDATE_1_CHECK;\r
          }\r
        }\r
        else\r
        {\r
          UPDATE_1_CHECK;\r
          prob = probs + IsRepG1 + state;\r
          IF_BIT_0_CHECK(prob)\r
          {\r
            UPDATE_0_CHECK;\r
          }\r
          else\r
          {\r
            UPDATE_1_CHECK;\r
            prob = probs + IsRepG2 + state;\r
            IF_BIT_0_CHECK(prob)\r
            {\r
              UPDATE_0_CHECK;\r
            }\r
            else\r
            {\r
              UPDATE_1_CHECK;\r
            }\r
          }\r
        }\r
        state = kNumStates;\r
        prob = probs + RepLenCoder;\r
      }\r
      {\r
        unsigned limit, offset;\r
        CLzmaProb *probLen = prob + LenChoice;\r
        IF_BIT_0_CHECK(probLen)\r
        {\r
          UPDATE_0_CHECK;\r
          probLen = prob + LenLow + (posState << kLenNumLowBits);\r
          offset = 0;\r
          limit = 1 << kLenNumLowBits;\r
        }\r
        else\r
        {\r
          UPDATE_1_CHECK;\r
          probLen = prob + LenChoice2;\r
          IF_BIT_0_CHECK(probLen)\r
          {\r
            UPDATE_0_CHECK;\r
            probLen = prob + LenMid + (posState << kLenNumMidBits);\r
            offset = kLenNumLowSymbols;\r
            limit = 1 << kLenNumMidBits;\r
          }\r
          else\r
          {\r
            UPDATE_1_CHECK;\r
            probLen = prob + LenHigh;\r
            offset = kLenNumLowSymbols + kLenNumMidSymbols;\r
            limit = 1 << kLenNumHighBits;\r
          }\r
        }\r
        TREE_DECODE_CHECK(probLen, limit, len);\r
        len += offset;\r
      }\r
\r
      if (state < 4)\r
      {\r
        unsigned posSlot;\r
        prob = probs + PosSlot +\r
            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<\r
            kNumPosSlotBits);\r
        TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);\r
        if (posSlot >= kStartPosModelIndex)\r
        {\r
          int numDirectBits = ((posSlot >> 1) - 1);\r
\r
          /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */\r
\r
          if (posSlot < kEndPosModelIndex)\r
          {\r
            prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;\r
          }\r
          else\r
          {\r
            numDirectBits -= kNumAlignBits;\r
            do\r
            {\r
              NORMALIZE_CHECK\r
              range >>= 1;\r
              code -= range & (((code - range) >> 31) - 1);\r
              /* if (code >= range) code -= range; */\r
            }\r
            while (--numDirectBits != 0);\r
            prob = probs + Align;\r
            numDirectBits = kNumAlignBits;\r
          }\r
          {\r
            unsigned i = 1;\r
            do\r
            {\r
              GET_BIT_CHECK(prob + i, i);\r
            }\r
            while (--numDirectBits != 0);\r
          }\r
        }\r
      }\r
    }\r
  }\r
  NORMALIZE_CHECK;\r
  return res;\r
}\r
\r
static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data)\r
{\r
  p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]);\r
  p->range = 0xFFFFFFFF;\r
  p->needFlush = 0;\r
}\r
\r
void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)\r
{\r
  p->needFlush = 1;\r
  p->remainLen = 0;\r
  p->tempBufSize = 0;\r
\r
  if (initDic)\r
  {\r
    p->processedPos = 0;\r
    p->checkDicSize = 0;\r
    p->needInitState = 1;\r
  }\r
  if (initState)\r
    p->needInitState = 1;\r
}\r
\r
void LzmaDec_Init(CLzmaDec *p)\r
{\r
  p->dicPos = 0;\r
  LzmaDec_InitDicAndState(p, True, True);\r
}\r
\r
static void LzmaDec_InitStateReal(CLzmaDec *p)\r
{\r
  UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));\r
  UInt32 i;\r
  CLzmaProb *probs = p->probs;\r
  for (i = 0; i < numProbs; i++)\r
    probs[i] = kBitModelTotal >> 1;\r
  p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;\r
  p->state = 0;\r
  p->needInitState = 0;\r
}\r
\r
SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,\r
    ELzmaFinishMode finishMode, ELzmaStatus *status)\r
{\r
  SizeT inSize = *srcLen;\r
  (*srcLen) = 0;\r
  LzmaDec_WriteRem(p, dicLimit);\r
  \r
  *status = LZMA_STATUS_NOT_SPECIFIED;\r
\r
  while (p->remainLen != kMatchSpecLenStart)\r
  {\r
      int checkEndMarkNow;\r
\r
      if (p->needFlush != 0)\r
      {\r
        for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)\r
          p->tempBuf[p->tempBufSize++] = *src++;\r
        if (p->tempBufSize < RC_INIT_SIZE)\r
        {\r
          *status = LZMA_STATUS_NEEDS_MORE_INPUT;\r
          return SZ_OK;\r
        }\r
        if (p->tempBuf[0] != 0)\r
          return SZ_ERROR_DATA;\r
\r
        LzmaDec_InitRc(p, p->tempBuf);\r
        p->tempBufSize = 0;\r
      }\r
\r
      checkEndMarkNow = 0;\r
      if (p->dicPos >= dicLimit)\r
      {\r
        if (p->remainLen == 0 && p->code == 0)\r
        {\r
          *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;\r
          return SZ_OK;\r
        }\r
        if (finishMode == LZMA_FINISH_ANY)\r
        {\r
          *status = LZMA_STATUS_NOT_FINISHED;\r
          return SZ_OK;\r
        }\r
        if (p->remainLen != 0)\r
        {\r
          *status = LZMA_STATUS_NOT_FINISHED;\r
          return SZ_ERROR_DATA;\r
        }\r
        checkEndMarkNow = 1;\r
      }\r
\r
      if (p->needInitState)\r
        LzmaDec_InitStateReal(p);\r
  \r
      if (p->tempBufSize == 0)\r
      {\r
        SizeT processed;\r
        const Byte *bufLimit;\r
        if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)\r
        {\r
          int dummyRes = LzmaDec_TryDummy(p, src, inSize);\r
          if (dummyRes == DUMMY_ERROR)\r
          {\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
          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)\r
          {\r
            *status = LZMA_STATUS_NOT_FINISHED;\r
            return SZ_ERROR_DATA;\r
          }\r
          bufLimit = src;\r
        }\r
        else\r
          bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;\r
        p->buf = src;\r
        if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)\r
          return SZ_ERROR_DATA;\r
        processed = (SizeT)(p->buf - src);\r
        (*srcLen) += processed;\r
        src += processed;\r
        inSize -= processed;\r
      }\r
      else\r
      {\r
        unsigned rem = p->tempBufSize, lookAhead = 0;\r
        while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)\r
          p->tempBuf[rem++] = src[lookAhead++];\r
        p->tempBufSize = rem;\r
        if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)\r
        {\r
          int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);\r
          if (dummyRes == DUMMY_ERROR)\r
          {\r
            (*srcLen) += lookAhead;\r
            *status = LZMA_STATUS_NEEDS_MORE_INPUT;\r
            return SZ_OK;\r
          }\r
          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)\r
          {\r
            *status = LZMA_STATUS_NOT_FINISHED;\r
            return SZ_ERROR_DATA;\r
          }\r
        }\r
        p->buf = p->tempBuf;\r
        if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)\r
          return SZ_ERROR_DATA;\r
        lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));\r
        (*srcLen) += lookAhead;\r
        src += lookAhead;\r
        inSize -= lookAhead;\r
        p->tempBufSize = 0;\r
      }\r
  }\r
  if (p->code == 0)\r
    *status = LZMA_STATUS_FINISHED_WITH_MARK;\r
  return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;\r
}\r
\r
SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)\r
{\r
  SizeT outSize = *destLen;\r
  SizeT inSize = *srcLen;\r
  *srcLen = *destLen = 0;\r
  for (;;)\r
  {\r
    SizeT inSizeCur = inSize, outSizeCur, dicPos;\r
    ELzmaFinishMode curFinishMode;\r
    SRes res;\r
    if (p->dicPos == p->dicBufSize)\r
      p->dicPos = 0;\r
    dicPos = p->dicPos;\r
    if (outSize > p->dicBufSize - dicPos)\r
    {\r
      outSizeCur = p->dicBufSize;\r
      curFinishMode = LZMA_FINISH_ANY;\r
    }\r
    else\r
    {\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
    if (outSizeCur == 0 || outSize == 0)\r
      return SZ_OK;\r
  }\r
}\r
\r
void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc)\r
{\r
  alloc->Free(alloc, p->probs);\r
  p->probs = 0;\r
}\r
\r
static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)\r
{\r
  alloc->Free(alloc, p->dic);\r
  p->dic = 0;\r
}\r
\r
void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)\r
{\r
  LzmaDec_FreeProbs(p, alloc);\r
  LzmaDec_FreeDict(p, alloc);\r
}\r
\r
SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)\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
  if (dicSize < LZMA_DIC_MIN)\r
    dicSize = LZMA_DIC_MIN;\r
  p->dicSize = dicSize;\r
\r
  d = data[0];\r
  if (d >= (9 * 5 * 5))\r
    return SZ_ERROR_UNSUPPORTED;\r
\r
  p->lc = d % 9;\r
  d /= 9;\r
  p->pb = d / 5;\r
  p->lp = d % 5;\r
\r
  return SZ_OK;\r
}\r
\r
static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc)\r
{\r
  UInt32 numProbs = LzmaProps_GetNumProbs(propNew);\r
  if (p->probs == 0 || numProbs != p->numProbs)\r
  {\r
    LzmaDec_FreeProbs(p, alloc);\r
    p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));\r
    p->numProbs = numProbs;\r
    if (p->probs == 0)\r
      return SZ_ERROR_MEM;\r
  }\r
  return SZ_OK;\r
}\r
\r
SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)\r
{\r
  CLzmaProps propNew;\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 LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)\r
{\r
  CLzmaProps propNew;\r
  SizeT dicBufSize;\r
  RINOK(LzmaProps_Decode(&propNew, props, propsSize));\r
  RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));\r
  dicBufSize = propNew.dicSize;\r
  if (p->dic == 0 || dicBufSize != p->dicBufSize)\r
  {\r
    LzmaDec_FreeDict(p, alloc);\r
    p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);\r
    if (p->dic == 0)\r
    {\r
      LzmaDec_FreeProbs(p, alloc);\r
      return SZ_ERROR_MEM;\r
    }\r
  }\r
  p->dicBufSize = dicBufSize;\r
  p->prop = propNew;\r
  return SZ_OK;\r
}\r
\r
SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,\r
    const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,\r
    ELzmaStatus *status, ISzAlloc *alloc)\r
{\r
  CLzmaDec p;\r
  SRes res;\r
  SizeT inSize = *srcLen;\r
  SizeT outSize = *destLen;\r
  *srcLen = *destLen = 0;\r
  if (inSize < RC_INIT_SIZE)\r
    return SZ_ERROR_INPUT_EOF;\r
\r
  LzmaDec_Construct(&p);\r
  res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc);\r
  if (res != 0)\r
    return res;\r
  p.dic = dest;\r
  p.dicBufSize = outSize;\r
\r
  LzmaDec_Init(&p);\r
  \r
  *srcLen = inSize;\r
  res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);\r
\r
  if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)\r
    res = SZ_ERROR_INPUT_EOF;\r
\r
  (*destLen) = p.dicPos;\r
  LzmaDec_FreeProbs(&p, alloc);\r
  return res;\r
}\r
\r