Home | History | Annotate | Download | only in C
      1 /** @file
      2   LzmaDec.c
      3 
      4   Based on LZMA SDK 4.65:
      5     LzmaDec.c -- LZMA Decoder
      6     2008-11-06 : Igor Pavlov : Public domain
      7 
      8   Copyright (c) 2009, Intel Corporation. All rights reserved.<BR>
      9   This program and the accompanying materials
     10   are licensed and made available under the terms and conditions of the BSD License
     11   which accompanies this distribution.  The full text of the license may be found at
     12   http://opensource.org/licenses/bsd-license.php
     13 
     14   THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
     15   WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
     16 
     17 **/
     18 
     19 #include "LzmaDec.h"
     20 
     21 #ifndef EFIAPI
     22 
     23 #include <string.h>
     24 
     25 #endif // !EFIAPI
     26 
     27 #define kNumTopBits 24
     28 #define kTopValue ((UInt32)1 << kNumTopBits)
     29 
     30 #define kNumBitModelTotalBits 11
     31 #define kBitModelTotal (1 << kNumBitModelTotalBits)
     32 #define kNumMoveBits 5
     33 
     34 #define RC_INIT_SIZE 5
     35 
     36 #define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }
     37 
     38 #define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
     39 #define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
     40 #define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
     41 #define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \
     42   { UPDATE_0(p); i = (i + i); A0; } else \
     43   { UPDATE_1(p); i = (i + i) + 1; A1; }
     44 #define GET_BIT(p, i) GET_BIT2(p, i, ; , ;)
     45 
     46 #define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); }
     47 #define TREE_DECODE(probs, limit, i) \
     48   { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }
     49 
     50 /* #define _LZMA_SIZE_OPT */
     51 
     52 #ifdef _LZMA_SIZE_OPT
     53 #define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
     54 #else
     55 #define TREE_6_DECODE(probs, i) \
     56   { i = 1; \
     57   TREE_GET_BIT(probs, i); \
     58   TREE_GET_BIT(probs, i); \
     59   TREE_GET_BIT(probs, i); \
     60   TREE_GET_BIT(probs, i); \
     61   TREE_GET_BIT(probs, i); \
     62   TREE_GET_BIT(probs, i); \
     63   i -= 0x40; }
     64 #endif
     65 
     66 #define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); }
     67 
     68 #define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
     69 #define UPDATE_0_CHECK range = bound;
     70 #define UPDATE_1_CHECK range -= bound; code -= bound;
     71 #define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \
     72   { UPDATE_0_CHECK; i = (i + i); A0; } else \
     73   { UPDATE_1_CHECK; i = (i + i) + 1; A1; }
     74 #define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;)
     75 #define TREE_DECODE_CHECK(probs, limit, i) \
     76   { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; }
     77 
     78 
     79 #define kNumPosBitsMax 4
     80 #define kNumPosStatesMax (1 << kNumPosBitsMax)
     81 
     82 #define kLenNumLowBits 3
     83 #define kLenNumLowSymbols (1 << kLenNumLowBits)
     84 #define kLenNumMidBits 3
     85 #define kLenNumMidSymbols (1 << kLenNumMidBits)
     86 #define kLenNumHighBits 8
     87 #define kLenNumHighSymbols (1 << kLenNumHighBits)
     88 
     89 #define LenChoice 0
     90 #define LenChoice2 (LenChoice + 1)
     91 #define LenLow (LenChoice2 + 1)
     92 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
     93 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
     94 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
     95 
     96 
     97 #define kNumStates 12
     98 #define kNumLitStates 7
     99 
    100 #define kStartPosModelIndex 4
    101 #define kEndPosModelIndex 14
    102 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
    103 
    104 #define kNumPosSlotBits 6
    105 #define kNumLenToPosStates 4
    106 
    107 #define kNumAlignBits 4
    108 #define kAlignTableSize (1 << kNumAlignBits)
    109 
    110 #define kMatchMinLen 2
    111 #define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
    112 
    113 #define IsMatch 0
    114 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
    115 #define IsRepG0 (IsRep + kNumStates)
    116 #define IsRepG1 (IsRepG0 + kNumStates)
    117 #define IsRepG2 (IsRepG1 + kNumStates)
    118 #define IsRep0Long (IsRepG2 + kNumStates)
    119 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
    120 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
    121 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
    122 #define LenCoder (Align + kAlignTableSize)
    123 #define RepLenCoder (LenCoder + kNumLenProbs)
    124 #define Literal (RepLenCoder + kNumLenProbs)
    125 
    126 #define LZMA_BASE_SIZE 1846
    127 #define LZMA_LIT_SIZE 768
    128 
    129 #define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
    130 
    131 #if Literal != LZMA_BASE_SIZE
    132 StopCompilingDueBUG
    133 #endif
    134 
    135 static const Byte kLiteralNextStates[kNumStates * 2] =
    136 {
    137   0, 0, 0, 0, 1, 2, 3,  4,  5,  6,  4,  5,
    138   7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10
    139 };
    140 
    141 #define LZMA_DIC_MIN (1 << 12)
    142 
    143 /* First LZMA-symbol is always decoded.
    144 And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization
    145 Out:
    146   Result:
    147     SZ_OK - OK
    148     SZ_ERROR_DATA - Error
    149   p->remainLen:
    150     < kMatchSpecLenStart : normal remain
    151     = kMatchSpecLenStart : finished
    152     = kMatchSpecLenStart + 1 : Flush marker
    153     = kMatchSpecLenStart + 2 : State Init Marker
    154 */
    155 
    156 static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
    157 {
    158   CLzmaProb *probs = p->probs;
    159 
    160   unsigned state = p->state;
    161   UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
    162   unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
    163   unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1;
    164   unsigned lc = p->prop.lc;
    165 
    166   Byte *dic = p->dic;
    167   SizeT dicBufSize = p->dicBufSize;
    168   SizeT dicPos = p->dicPos;
    169 
    170   UInt32 processedPos = p->processedPos;
    171   UInt32 checkDicSize = p->checkDicSize;
    172   unsigned len = 0;
    173 
    174   const Byte *buf = p->buf;
    175   UInt32 range = p->range;
    176   UInt32 code = p->code;
    177 
    178   do
    179   {
    180     CLzmaProb *prob;
    181     UInt32 bound;
    182     unsigned ttt;
    183     unsigned posState = processedPos & pbMask;
    184 
    185     prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
    186     IF_BIT_0(prob)
    187     {
    188       unsigned symbol;
    189       UPDATE_0(prob);
    190       prob = probs + Literal;
    191       if (checkDicSize != 0 || processedPos != 0)
    192         prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) +
    193         (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));
    194 
    195       if (state < kNumLitStates)
    196       {
    197         symbol = 1;
    198         do { GET_BIT(prob + symbol, symbol) } while (symbol < 0x100);
    199       }
    200       else
    201       {
    202         unsigned matchByte = p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
    203         unsigned offs = 0x100;
    204         symbol = 1;
    205         do
    206         {
    207           unsigned bit;
    208           CLzmaProb *probLit;
    209           matchByte <<= 1;
    210           bit = (matchByte & offs);
    211           probLit = prob + offs + bit + symbol;
    212           GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)
    213         }
    214         while (symbol < 0x100);
    215       }
    216       dic[dicPos++] = (Byte)symbol;
    217       processedPos++;
    218 
    219       state = kLiteralNextStates[state];
    220       /* if (state < 4) state = 0; else if (state < 10) state -= 3; else state -= 6; */
    221       continue;
    222     }
    223     else
    224     {
    225       UPDATE_1(prob);
    226       prob = probs + IsRep + state;
    227       IF_BIT_0(prob)
    228       {
    229         UPDATE_0(prob);
    230         state += kNumStates;
    231         prob = probs + LenCoder;
    232       }
    233       else
    234       {
    235         UPDATE_1(prob);
    236         if (checkDicSize == 0 && processedPos == 0)
    237           return SZ_ERROR_DATA;
    238         prob = probs + IsRepG0 + state;
    239         IF_BIT_0(prob)
    240         {
    241           UPDATE_0(prob);
    242           prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
    243           IF_BIT_0(prob)
    244           {
    245             UPDATE_0(prob);
    246             dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
    247             dicPos++;
    248             processedPos++;
    249             state = state < kNumLitStates ? 9 : 11;
    250             continue;
    251           }
    252           UPDATE_1(prob);
    253         }
    254         else
    255         {
    256           UInt32 distance;
    257           UPDATE_1(prob);
    258           prob = probs + IsRepG1 + state;
    259           IF_BIT_0(prob)
    260           {
    261             UPDATE_0(prob);
    262             distance = rep1;
    263           }
    264           else
    265           {
    266             UPDATE_1(prob);
    267             prob = probs + IsRepG2 + state;
    268             IF_BIT_0(prob)
    269             {
    270               UPDATE_0(prob);
    271               distance = rep2;
    272             }
    273             else
    274             {
    275               UPDATE_1(prob);
    276               distance = rep3;
    277               rep3 = rep2;
    278             }
    279             rep2 = rep1;
    280           }
    281           rep1 = rep0;
    282           rep0 = distance;
    283         }
    284         state = state < kNumLitStates ? 8 : 11;
    285         prob = probs + RepLenCoder;
    286       }
    287       {
    288         unsigned limit2, offset;
    289         CLzmaProb *probLen = prob + LenChoice;
    290         IF_BIT_0(probLen)
    291         {
    292           UPDATE_0(probLen);
    293           probLen = prob + LenLow + (posState << kLenNumLowBits);
    294           offset = 0;
    295           limit2 = (1 << kLenNumLowBits);
    296         }
    297         else
    298         {
    299           UPDATE_1(probLen);
    300           probLen = prob + LenChoice2;
    301           IF_BIT_0(probLen)
    302           {
    303             UPDATE_0(probLen);
    304             probLen = prob + LenMid + (posState << kLenNumMidBits);
    305             offset = kLenNumLowSymbols;
    306             limit2 = (1 << kLenNumMidBits);
    307           }
    308           else
    309           {
    310             UPDATE_1(probLen);
    311             probLen = prob + LenHigh;
    312             offset = kLenNumLowSymbols + kLenNumMidSymbols;
    313             limit2 = (1 << kLenNumHighBits);
    314           }
    315         }
    316         TREE_DECODE(probLen, limit2, len);
    317         len += offset;
    318       }
    319 
    320       if (state >= kNumStates)
    321       {
    322         UInt32 distance;
    323         prob = probs + PosSlot +
    324             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
    325         TREE_6_DECODE(prob, distance);
    326         if (distance >= kStartPosModelIndex)
    327         {
    328           unsigned posSlot = (unsigned)distance;
    329           int numDirectBits = (int)(((distance >> 1) - 1));
    330           distance = (2 | (distance & 1));
    331           if (posSlot < kEndPosModelIndex)
    332           {
    333             distance <<= numDirectBits;
    334             prob = probs + SpecPos + distance - posSlot - 1;
    335             {
    336               UInt32 mask = 1;
    337               unsigned i = 1;
    338               do
    339               {
    340                 GET_BIT2(prob + i, i, ; , distance |= mask);
    341                 mask <<= 1;
    342               }
    343               while (--numDirectBits != 0);
    344             }
    345           }
    346           else
    347           {
    348             numDirectBits -= kNumAlignBits;
    349             do
    350             {
    351               NORMALIZE
    352               range >>= 1;
    353 
    354               {
    355                 UInt32 t;
    356                 code -= range;
    357                 t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
    358                 distance = (distance << 1) + (t + 1);
    359                 code += range & t;
    360               }
    361               /*
    362               distance <<= 1;
    363               if (code >= range)
    364               {
    365                 code -= range;
    366                 distance |= 1;
    367               }
    368               */
    369             }
    370             while (--numDirectBits != 0);
    371             prob = probs + Align;
    372             distance <<= kNumAlignBits;
    373             {
    374               unsigned i = 1;
    375               GET_BIT2(prob + i, i, ; , distance |= 1);
    376               GET_BIT2(prob + i, i, ; , distance |= 2);
    377               GET_BIT2(prob + i, i, ; , distance |= 4);
    378               GET_BIT2(prob + i, i, ; , distance |= 8);
    379             }
    380             if (distance == (UInt32)0xFFFFFFFF)
    381             {
    382               len += kMatchSpecLenStart;
    383               state -= kNumStates;
    384               break;
    385             }
    386           }
    387         }
    388         rep3 = rep2;
    389         rep2 = rep1;
    390         rep1 = rep0;
    391         rep0 = distance + 1;
    392         if (checkDicSize == 0)
    393         {
    394           if (distance >= processedPos)
    395             return SZ_ERROR_DATA;
    396         }
    397         else if (distance >= checkDicSize)
    398           return SZ_ERROR_DATA;
    399         state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
    400         /* state = kLiteralNextStates[state]; */
    401       }
    402 
    403       len += kMatchMinLen;
    404 
    405       if (limit == dicPos)
    406         return SZ_ERROR_DATA;
    407       {
    408         SizeT rem = limit - dicPos;
    409         unsigned curLen = ((rem < len) ? (unsigned)rem : len);
    410         SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
    411 
    412         processedPos += curLen;
    413 
    414         len -= curLen;
    415         if (pos + curLen <= dicBufSize)
    416         {
    417           Byte *dest = dic + dicPos;
    418           ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
    419           const Byte *lim = dest + curLen;
    420           dicPos += curLen;
    421           do
    422             *((volatile Byte *)dest) = (Byte)*(dest + src);
    423           while (++dest != lim);
    424         }
    425         else
    426         {
    427           do
    428           {
    429             dic[dicPos++] = dic[pos];
    430             if (++pos == dicBufSize)
    431               pos = 0;
    432           }
    433           while (--curLen != 0);
    434         }
    435       }
    436     }
    437   }
    438   while (dicPos < limit && buf < bufLimit);
    439   NORMALIZE;
    440   p->buf = buf;
    441   p->range = range;
    442   p->code = code;
    443   p->remainLen = len;
    444   p->dicPos = dicPos;
    445   p->processedPos = processedPos;
    446   p->reps[0] = rep0;
    447   p->reps[1] = rep1;
    448   p->reps[2] = rep2;
    449   p->reps[3] = rep3;
    450   p->state = state;
    451 
    452   return SZ_OK;
    453 }
    454 
    455 static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)
    456 {
    457   if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
    458   {
    459     Byte *dic = p->dic;
    460     SizeT dicPos = p->dicPos;
    461     SizeT dicBufSize = p->dicBufSize;
    462     unsigned len = p->remainLen;
    463     UInt32 rep0 = p->reps[0];
    464     if (limit - dicPos < len)
    465       len = (unsigned)(limit - dicPos);
    466 
    467     if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
    468       p->checkDicSize = p->prop.dicSize;
    469 
    470     p->processedPos += len;
    471     p->remainLen -= len;
    472     while (len-- != 0)
    473     {
    474       dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
    475       dicPos++;
    476     }
    477     p->dicPos = dicPos;
    478   }
    479 }
    480 
    481 static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
    482 {
    483   do
    484   {
    485     SizeT limit2 = limit;
    486     if (p->checkDicSize == 0)
    487     {
    488       UInt32 rem = p->prop.dicSize - p->processedPos;
    489       if (limit - p->dicPos > rem)
    490         limit2 = p->dicPos + rem;
    491     }
    492     RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));
    493     if (p->processedPos >= p->prop.dicSize)
    494       p->checkDicSize = p->prop.dicSize;
    495     LzmaDec_WriteRem(p, limit);
    496   }
    497   while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
    498 
    499   if (p->remainLen > kMatchSpecLenStart)
    500   {
    501     p->remainLen = kMatchSpecLenStart;
    502   }
    503   return 0;
    504 }
    505 
    506 typedef enum
    507 {
    508   DUMMY_ERROR, /* unexpected end of input stream */
    509   DUMMY_LIT,
    510   DUMMY_MATCH,
    511   DUMMY_REP
    512 } ELzmaDummy;
    513 
    514 static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)
    515 {
    516   UInt32 range = p->range;
    517   UInt32 code = p->code;
    518   const Byte *bufLimit = buf + inSize;
    519   CLzmaProb *probs = p->probs;
    520   unsigned state = p->state;
    521   ELzmaDummy res;
    522 
    523   {
    524     CLzmaProb *prob;
    525     UInt32 bound;
    526     unsigned ttt;
    527     unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);
    528 
    529     prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
    530     IF_BIT_0_CHECK(prob)
    531     {
    532       UPDATE_0_CHECK
    533 
    534       /* if (bufLimit - buf >= 7) return DUMMY_LIT; */
    535 
    536       prob = probs + Literal;
    537       if (p->checkDicSize != 0 || p->processedPos != 0)
    538         prob += (LZMA_LIT_SIZE *
    539           ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
    540           (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
    541 
    542       if (state < kNumLitStates)
    543       {
    544         unsigned symbol = 1;
    545         do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);
    546       }
    547       else
    548       {
    549         unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
    550             ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)];
    551         unsigned offs = 0x100;
    552         unsigned symbol = 1;
    553         do
    554         {
    555           unsigned bit;
    556           CLzmaProb *probLit;
    557           matchByte <<= 1;
    558           bit = (matchByte & offs);
    559           probLit = prob + offs + bit + symbol;
    560           GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)
    561         }
    562         while (symbol < 0x100);
    563       }
    564       res = DUMMY_LIT;
    565     }
    566     else
    567     {
    568       unsigned len;
    569       UPDATE_1_CHECK;
    570 
    571       prob = probs + IsRep + state;
    572       IF_BIT_0_CHECK(prob)
    573       {
    574         UPDATE_0_CHECK;
    575         state = 0;
    576         prob = probs + LenCoder;
    577         res = DUMMY_MATCH;
    578       }
    579       else
    580       {
    581         UPDATE_1_CHECK;
    582         res = DUMMY_REP;
    583         prob = probs + IsRepG0 + state;
    584         IF_BIT_0_CHECK(prob)
    585         {
    586           UPDATE_0_CHECK;
    587           prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
    588           IF_BIT_0_CHECK(prob)
    589           {
    590             UPDATE_0_CHECK;
    591             NORMALIZE_CHECK;
    592             return DUMMY_REP;
    593           }
    594           else
    595           {
    596             UPDATE_1_CHECK;
    597           }
    598         }
    599         else
    600         {
    601           UPDATE_1_CHECK;
    602           prob = probs + IsRepG1 + state;
    603           IF_BIT_0_CHECK(prob)
    604           {
    605             UPDATE_0_CHECK;
    606           }
    607           else
    608           {
    609             UPDATE_1_CHECK;
    610             prob = probs + IsRepG2 + state;
    611             IF_BIT_0_CHECK(prob)
    612             {
    613               UPDATE_0_CHECK;
    614             }
    615             else
    616             {
    617               UPDATE_1_CHECK;
    618             }
    619           }
    620         }
    621         state = kNumStates;
    622         prob = probs + RepLenCoder;
    623       }
    624       {
    625         unsigned limit, offset;
    626         CLzmaProb *probLen = prob + LenChoice;
    627         IF_BIT_0_CHECK(probLen)
    628         {
    629           UPDATE_0_CHECK;
    630           probLen = prob + LenLow + (posState << kLenNumLowBits);
    631           offset = 0;
    632           limit = 1 << kLenNumLowBits;
    633         }
    634         else
    635         {
    636           UPDATE_1_CHECK;
    637           probLen = prob + LenChoice2;
    638           IF_BIT_0_CHECK(probLen)
    639           {
    640             UPDATE_0_CHECK;
    641             probLen = prob + LenMid + (posState << kLenNumMidBits);
    642             offset = kLenNumLowSymbols;
    643             limit = 1 << kLenNumMidBits;
    644           }
    645           else
    646           {
    647             UPDATE_1_CHECK;
    648             probLen = prob + LenHigh;
    649             offset = kLenNumLowSymbols + kLenNumMidSymbols;
    650             limit = 1 << kLenNumHighBits;
    651           }
    652         }
    653         TREE_DECODE_CHECK(probLen, limit, len);
    654         len += offset;
    655       }
    656 
    657       if (state < 4)
    658       {
    659         unsigned posSlot;
    660         prob = probs + PosSlot +
    661             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
    662             kNumPosSlotBits);
    663         TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
    664         if (posSlot >= kStartPosModelIndex)
    665         {
    666           int numDirectBits = ((posSlot >> 1) - 1);
    667 
    668           /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
    669 
    670           if (posSlot < kEndPosModelIndex)
    671           {
    672             prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;
    673           }
    674           else
    675           {
    676             numDirectBits -= kNumAlignBits;
    677             do
    678             {
    679               NORMALIZE_CHECK
    680               range >>= 1;
    681               code -= range & (((code - range) >> 31) - 1);
    682               /* if (code >= range) code -= range; */
    683             }
    684             while (--numDirectBits != 0);
    685             prob = probs + Align;
    686             numDirectBits = kNumAlignBits;
    687           }
    688           {
    689             unsigned i = 1;
    690             do
    691             {
    692               GET_BIT_CHECK(prob + i, i);
    693             }
    694             while (--numDirectBits != 0);
    695           }
    696         }
    697       }
    698     }
    699   }
    700   NORMALIZE_CHECK;
    701   return res;
    702 }
    703 
    704 static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data)
    705 {
    706   p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]);
    707   p->range = 0xFFFFFFFF;
    708   p->needFlush = 0;
    709 }
    710 
    711 void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)
    712 {
    713   p->needFlush = 1;
    714   p->remainLen = 0;
    715   p->tempBufSize = 0;
    716 
    717   if (initDic)
    718   {
    719     p->processedPos = 0;
    720     p->checkDicSize = 0;
    721     p->needInitState = 1;
    722   }
    723   if (initState)
    724     p->needInitState = 1;
    725 }
    726 
    727 void LzmaDec_Init(CLzmaDec *p)
    728 {
    729   p->dicPos = 0;
    730   LzmaDec_InitDicAndState(p, True, True);
    731 }
    732 
    733 static void LzmaDec_InitStateReal(CLzmaDec *p)
    734 {
    735   UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
    736   UInt32 i;
    737   CLzmaProb *probs = p->probs;
    738   for (i = 0; i < numProbs; i++)
    739     probs[i] = kBitModelTotal >> 1;
    740   p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
    741   p->state = 0;
    742   p->needInitState = 0;
    743 }
    744 
    745 SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,
    746     ELzmaFinishMode finishMode, ELzmaStatus *status)
    747 {
    748   SizeT inSize = *srcLen;
    749   (*srcLen) = 0;
    750   LzmaDec_WriteRem(p, dicLimit);
    751 
    752   *status = LZMA_STATUS_NOT_SPECIFIED;
    753 
    754   while (p->remainLen != kMatchSpecLenStart)
    755   {
    756       int checkEndMarkNow;
    757 
    758       if (p->needFlush != 0)
    759       {
    760         for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
    761           p->tempBuf[p->tempBufSize++] = *src++;
    762         if (p->tempBufSize < RC_INIT_SIZE)
    763         {
    764           *status = LZMA_STATUS_NEEDS_MORE_INPUT;
    765           return SZ_OK;
    766         }
    767         if (p->tempBuf[0] != 0)
    768           return SZ_ERROR_DATA;
    769 
    770         LzmaDec_InitRc(p, p->tempBuf);
    771         p->tempBufSize = 0;
    772       }
    773 
    774       checkEndMarkNow = 0;
    775       if (p->dicPos >= dicLimit)
    776       {
    777         if (p->remainLen == 0 && p->code == 0)
    778         {
    779           *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
    780           return SZ_OK;
    781         }
    782         if (finishMode == LZMA_FINISH_ANY)
    783         {
    784           *status = LZMA_STATUS_NOT_FINISHED;
    785           return SZ_OK;
    786         }
    787         if (p->remainLen != 0)
    788         {
    789           *status = LZMA_STATUS_NOT_FINISHED;
    790           return SZ_ERROR_DATA;
    791         }
    792         checkEndMarkNow = 1;
    793       }
    794 
    795       if (p->needInitState)
    796         LzmaDec_InitStateReal(p);
    797 
    798       if (p->tempBufSize == 0)
    799       {
    800         SizeT processed;
    801         const Byte *bufLimit;
    802         if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
    803         {
    804           int dummyRes = LzmaDec_TryDummy(p, src, inSize);
    805           if (dummyRes == DUMMY_ERROR)
    806           {
    807             memcpy(p->tempBuf, src, inSize);
    808             p->tempBufSize = (unsigned)inSize;
    809             (*srcLen) += inSize;
    810             *status = LZMA_STATUS_NEEDS_MORE_INPUT;
    811             return SZ_OK;
    812           }
    813           if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
    814           {
    815             *status = LZMA_STATUS_NOT_FINISHED;
    816             return SZ_ERROR_DATA;
    817           }
    818           bufLimit = src;
    819         }
    820         else
    821           bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
    822         p->buf = src;
    823         if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
    824           return SZ_ERROR_DATA;
    825         processed = (SizeT)(p->buf - src);
    826         (*srcLen) += processed;
    827         src += processed;
    828         inSize -= processed;
    829       }
    830       else
    831       {
    832         unsigned rem = p->tempBufSize, lookAhead = 0;
    833         while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
    834           p->tempBuf[rem++] = src[lookAhead++];
    835         p->tempBufSize = rem;
    836         if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
    837         {
    838           int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
    839           if (dummyRes == DUMMY_ERROR)
    840           {
    841             (*srcLen) += lookAhead;
    842             *status = LZMA_STATUS_NEEDS_MORE_INPUT;
    843             return SZ_OK;
    844           }
    845           if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
    846           {
    847             *status = LZMA_STATUS_NOT_FINISHED;
    848             return SZ_ERROR_DATA;
    849           }
    850         }
    851         p->buf = p->tempBuf;
    852         if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
    853           return SZ_ERROR_DATA;
    854         lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));
    855         (*srcLen) += lookAhead;
    856         src += lookAhead;
    857         inSize -= lookAhead;
    858         p->tempBufSize = 0;
    859       }
    860   }
    861   if (p->code == 0)
    862     *status = LZMA_STATUS_FINISHED_WITH_MARK;
    863   return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;
    864 }
    865 
    866 SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
    867 {
    868   SizeT outSize = *destLen;
    869   SizeT inSize = *srcLen;
    870   *srcLen = *destLen = 0;
    871   for (;;)
    872   {
    873     SizeT inSizeCur = inSize, outSizeCur, dicPos;
    874     ELzmaFinishMode curFinishMode;
    875     SRes res;
    876     if (p->dicPos == p->dicBufSize)
    877       p->dicPos = 0;
    878     dicPos = p->dicPos;
    879     if (outSize > p->dicBufSize - dicPos)
    880     {
    881       outSizeCur = p->dicBufSize;
    882       curFinishMode = LZMA_FINISH_ANY;
    883     }
    884     else
    885     {
    886       outSizeCur = dicPos + outSize;
    887       curFinishMode = finishMode;
    888     }
    889 
    890     res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
    891     src += inSizeCur;
    892     inSize -= inSizeCur;
    893     *srcLen += inSizeCur;
    894     outSizeCur = p->dicPos - dicPos;
    895     memcpy(dest, p->dic + dicPos, outSizeCur);
    896     dest += outSizeCur;
    897     outSize -= outSizeCur;
    898     *destLen += outSizeCur;
    899     if (res != 0)
    900       return res;
    901     if (outSizeCur == 0 || outSize == 0)
    902       return SZ_OK;
    903   }
    904 }
    905 
    906 void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc)
    907 {
    908   alloc->Free(alloc, p->probs);
    909   p->probs = 0;
    910 }
    911 
    912 static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)
    913 {
    914   alloc->Free(alloc, p->dic);
    915   p->dic = 0;
    916 }
    917 
    918 void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)
    919 {
    920   LzmaDec_FreeProbs(p, alloc);
    921   LzmaDec_FreeDict(p, alloc);
    922 }
    923 
    924 SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
    925 {
    926   UInt32 dicSize;
    927   Byte d;
    928 
    929   if (size < LZMA_PROPS_SIZE)
    930     return SZ_ERROR_UNSUPPORTED;
    931   else
    932     dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
    933 
    934   if (dicSize < LZMA_DIC_MIN)
    935     dicSize = LZMA_DIC_MIN;
    936   p->dicSize = dicSize;
    937 
    938   d = data[0];
    939   if (d >= (9 * 5 * 5))
    940     return SZ_ERROR_UNSUPPORTED;
    941 
    942   p->lc = d % 9;
    943   d /= 9;
    944   p->pb = d / 5;
    945   p->lp = d % 5;
    946 
    947   return SZ_OK;
    948 }
    949 
    950 static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc)
    951 {
    952   UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
    953   if (p->probs == 0 || numProbs != p->numProbs)
    954   {
    955     LzmaDec_FreeProbs(p, alloc);
    956     p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));
    957     p->numProbs = numProbs;
    958     if (p->probs == 0)
    959       return SZ_ERROR_MEM;
    960   }
    961   return SZ_OK;
    962 }
    963 
    964 SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
    965 {
    966   CLzmaProps propNew;
    967   RINOK(LzmaProps_Decode(&propNew, props, propsSize));
    968   RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
    969   p->prop = propNew;
    970   return SZ_OK;
    971 }
    972 
    973 SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
    974 {
    975   CLzmaProps propNew;
    976   SizeT dicBufSize;
    977   RINOK(LzmaProps_Decode(&propNew, props, propsSize));
    978   RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
    979   dicBufSize = propNew.dicSize;
    980   if (p->dic == 0 || dicBufSize != p->dicBufSize)
    981   {
    982     LzmaDec_FreeDict(p, alloc);
    983     p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);
    984     if (p->dic == 0)
    985     {
    986       LzmaDec_FreeProbs(p, alloc);
    987       return SZ_ERROR_MEM;
    988     }
    989   }
    990   p->dicBufSize = dicBufSize;
    991   p->prop = propNew;
    992   return SZ_OK;
    993 }
    994 
    995 SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
    996     const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
    997     ELzmaStatus *status, ISzAlloc *alloc)
    998 {
    999   CLzmaDec p;
   1000   SRes res;
   1001   SizeT inSize = *srcLen;
   1002   SizeT outSize = *destLen;
   1003   *srcLen = *destLen = 0;
   1004   if (inSize < RC_INIT_SIZE)
   1005     return SZ_ERROR_INPUT_EOF;
   1006 
   1007   LzmaDec_Construct(&p);
   1008   res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc);
   1009   if (res != 0)
   1010     return res;
   1011   p.dic = dest;
   1012   p.dicBufSize = outSize;
   1013 
   1014   LzmaDec_Init(&p);
   1015 
   1016   *srcLen = inSize;
   1017   res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
   1018 
   1019   if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
   1020     res = SZ_ERROR_INPUT_EOF;
   1021 
   1022   (*destLen) = p.dicPos;
   1023   LzmaDec_FreeProbs(&p, alloc);
   1024   return res;
   1025 }
   1026 
   1027