1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/win32/7zip/7z/C/LzmaDec.c	Sat Mar 03 10:31:27 2012 -0600
     1.3 @@ -0,0 +1,1007 @@
     1.4 +/* LzmaDec.c -- LZMA Decoder
     1.5 +2008-11-06 : Igor Pavlov : Public domain */
     1.6 +
     1.7 +#include "LzmaDec.h"
     1.8 +
     1.9 +#include <string.h>
    1.10 +
    1.11 +#define kNumTopBits 24
    1.12 +#define kTopValue ((UInt32)1 << kNumTopBits)
    1.13 +
    1.14 +#define kNumBitModelTotalBits 11
    1.15 +#define kBitModelTotal (1 << kNumBitModelTotalBits)
    1.16 +#define kNumMoveBits 5
    1.17 +
    1.18 +#define RC_INIT_SIZE 5
    1.19 +
    1.20 +#define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }
    1.21 +
    1.22 +#define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
    1.23 +#define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
    1.24 +#define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
    1.25 +#define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \
    1.26 +  { UPDATE_0(p); i = (i + i); A0; } else \
    1.27 +  { UPDATE_1(p); i = (i + i) + 1; A1; }
    1.28 +#define GET_BIT(p, i) GET_BIT2(p, i, ; , ;)
    1.29 +
    1.30 +#define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); }
    1.31 +#define TREE_DECODE(probs, limit, i) \
    1.32 +  { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }
    1.33 +
    1.34 +/* #define _LZMA_SIZE_OPT */
    1.35 +
    1.36 +#ifdef _LZMA_SIZE_OPT
    1.37 +#define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
    1.38 +#else
    1.39 +#define TREE_6_DECODE(probs, i) \
    1.40 +  { i = 1; \
    1.41 +  TREE_GET_BIT(probs, i); \
    1.42 +  TREE_GET_BIT(probs, i); \
    1.43 +  TREE_GET_BIT(probs, i); \
    1.44 +  TREE_GET_BIT(probs, i); \
    1.45 +  TREE_GET_BIT(probs, i); \
    1.46 +  TREE_GET_BIT(probs, i); \
    1.47 +  i -= 0x40; }
    1.48 +#endif
    1.49 +
    1.50 +#define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); }
    1.51 +
    1.52 +#define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
    1.53 +#define UPDATE_0_CHECK range = bound;
    1.54 +#define UPDATE_1_CHECK range -= bound; code -= bound;
    1.55 +#define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \
    1.56 +  { UPDATE_0_CHECK; i = (i + i); A0; } else \
    1.57 +  { UPDATE_1_CHECK; i = (i + i) + 1; A1; }
    1.58 +#define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;)
    1.59 +#define TREE_DECODE_CHECK(probs, limit, i) \
    1.60 +  { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; }
    1.61 +
    1.62 +
    1.63 +#define kNumPosBitsMax 4
    1.64 +#define kNumPosStatesMax (1 << kNumPosBitsMax)
    1.65 +
    1.66 +#define kLenNumLowBits 3
    1.67 +#define kLenNumLowSymbols (1 << kLenNumLowBits)
    1.68 +#define kLenNumMidBits 3
    1.69 +#define kLenNumMidSymbols (1 << kLenNumMidBits)
    1.70 +#define kLenNumHighBits 8
    1.71 +#define kLenNumHighSymbols (1 << kLenNumHighBits)
    1.72 +
    1.73 +#define LenChoice 0
    1.74 +#define LenChoice2 (LenChoice + 1)
    1.75 +#define LenLow (LenChoice2 + 1)
    1.76 +#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
    1.77 +#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
    1.78 +#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
    1.79 +
    1.80 +
    1.81 +#define kNumStates 12
    1.82 +#define kNumLitStates 7
    1.83 +
    1.84 +#define kStartPosModelIndex 4
    1.85 +#define kEndPosModelIndex 14
    1.86 +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
    1.87 +
    1.88 +#define kNumPosSlotBits 6
    1.89 +#define kNumLenToPosStates 4
    1.90 +
    1.91 +#define kNumAlignBits 4
    1.92 +#define kAlignTableSize (1 << kNumAlignBits)
    1.93 +
    1.94 +#define kMatchMinLen 2
    1.95 +#define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
    1.96 +
    1.97 +#define IsMatch 0
    1.98 +#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
    1.99 +#define IsRepG0 (IsRep + kNumStates)
   1.100 +#define IsRepG1 (IsRepG0 + kNumStates)
   1.101 +#define IsRepG2 (IsRepG1 + kNumStates)
   1.102 +#define IsRep0Long (IsRepG2 + kNumStates)
   1.103 +#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
   1.104 +#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
   1.105 +#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
   1.106 +#define LenCoder (Align + kAlignTableSize)
   1.107 +#define RepLenCoder (LenCoder + kNumLenProbs)
   1.108 +#define Literal (RepLenCoder + kNumLenProbs)
   1.109 +
   1.110 +#define LZMA_BASE_SIZE 1846
   1.111 +#define LZMA_LIT_SIZE 768
   1.112 +
   1.113 +#define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
   1.114 +
   1.115 +#if Literal != LZMA_BASE_SIZE
   1.116 +StopCompilingDueBUG
   1.117 +#endif
   1.118 +
   1.119 +static const Byte kLiteralNextStates[kNumStates * 2] =
   1.120 +{
   1.121 +  0, 0, 0, 0, 1, 2, 3,  4,  5,  6,  4,  5,
   1.122 +  7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10
   1.123 +};
   1.124 +
   1.125 +#define LZMA_DIC_MIN (1 << 12)
   1.126 +
   1.127 +/* First LZMA-symbol is always decoded.
   1.128 +And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization
   1.129 +Out:
   1.130 +  Result:
   1.131 +    SZ_OK - OK
   1.132 +    SZ_ERROR_DATA - Error
   1.133 +  p->remainLen:
   1.134 +    < kMatchSpecLenStart : normal remain
   1.135 +    = kMatchSpecLenStart : finished
   1.136 +    = kMatchSpecLenStart + 1 : Flush marker
   1.137 +    = kMatchSpecLenStart + 2 : State Init Marker
   1.138 +*/
   1.139 +
   1.140 +static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
   1.141 +{
   1.142 +  CLzmaProb *probs = p->probs;
   1.143 +
   1.144 +  unsigned state = p->state;
   1.145 +  UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
   1.146 +  unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
   1.147 +  unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1;
   1.148 +  unsigned lc = p->prop.lc;
   1.149 +
   1.150 +  Byte *dic = p->dic;
   1.151 +  SizeT dicBufSize = p->dicBufSize;
   1.152 +  SizeT dicPos = p->dicPos;
   1.153 +  
   1.154 +  UInt32 processedPos = p->processedPos;
   1.155 +  UInt32 checkDicSize = p->checkDicSize;
   1.156 +  unsigned len = 0;
   1.157 +
   1.158 +  const Byte *buf = p->buf;
   1.159 +  UInt32 range = p->range;
   1.160 +  UInt32 code = p->code;
   1.161 +
   1.162 +  do
   1.163 +  {
   1.164 +    CLzmaProb *prob;
   1.165 +    UInt32 bound;
   1.166 +    unsigned ttt;
   1.167 +    unsigned posState = processedPos & pbMask;
   1.168 +
   1.169 +    prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
   1.170 +    IF_BIT_0(prob)
   1.171 +    {
   1.172 +      unsigned symbol;
   1.173 +      UPDATE_0(prob);
   1.174 +      prob = probs + Literal;
   1.175 +      if (checkDicSize != 0 || processedPos != 0)
   1.176 +        prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) +
   1.177 +        (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));
   1.178 +
   1.179 +      if (state < kNumLitStates)
   1.180 +      {
   1.181 +        symbol = 1;
   1.182 +        do { GET_BIT(prob + symbol, symbol) } while (symbol < 0x100);
   1.183 +      }
   1.184 +      else
   1.185 +      {
   1.186 +        unsigned matchByte = p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
   1.187 +        unsigned offs = 0x100;
   1.188 +        symbol = 1;
   1.189 +        do
   1.190 +        {
   1.191 +          unsigned bit;
   1.192 +          CLzmaProb *probLit;
   1.193 +          matchByte <<= 1;
   1.194 +          bit = (matchByte & offs);
   1.195 +          probLit = prob + offs + bit + symbol;
   1.196 +          GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)
   1.197 +        }
   1.198 +        while (symbol < 0x100);
   1.199 +      }
   1.200 +      dic[dicPos++] = (Byte)(symbol & 0xFF);
   1.201 +      processedPos++;
   1.202 +
   1.203 +      state = kLiteralNextStates[state];
   1.204 +      /* if (state < 4) state = 0; else if (state < 10) state -= 3; else state -= 6; */
   1.205 +      continue;
   1.206 +    }
   1.207 +    else
   1.208 +    {
   1.209 +      UPDATE_1(prob);
   1.210 +      prob = probs + IsRep + state;
   1.211 +      IF_BIT_0(prob)
   1.212 +      {
   1.213 +        UPDATE_0(prob);
   1.214 +        state += kNumStates;
   1.215 +        prob = probs + LenCoder;
   1.216 +      }
   1.217 +      else
   1.218 +      {
   1.219 +        UPDATE_1(prob);
   1.220 +        if (checkDicSize == 0 && processedPos == 0)
   1.221 +          return SZ_ERROR_DATA;
   1.222 +        prob = probs + IsRepG0 + state;
   1.223 +        IF_BIT_0(prob)
   1.224 +        {
   1.225 +          UPDATE_0(prob);
   1.226 +          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
   1.227 +          IF_BIT_0(prob)
   1.228 +          {
   1.229 +            UPDATE_0(prob);
   1.230 +            dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
   1.231 +            dicPos++;
   1.232 +            processedPos++;
   1.233 +            state = state < kNumLitStates ? 9 : 11;
   1.234 +            continue;
   1.235 +          }
   1.236 +          UPDATE_1(prob);
   1.237 +        }
   1.238 +        else
   1.239 +        {
   1.240 +          UInt32 distance;
   1.241 +          UPDATE_1(prob);
   1.242 +          prob = probs + IsRepG1 + state;
   1.243 +          IF_BIT_0(prob)
   1.244 +          {
   1.245 +            UPDATE_0(prob);
   1.246 +            distance = rep1;
   1.247 +          }
   1.248 +          else
   1.249 +          {
   1.250 +            UPDATE_1(prob);
   1.251 +            prob = probs + IsRepG2 + state;
   1.252 +            IF_BIT_0(prob)
   1.253 +            {
   1.254 +              UPDATE_0(prob);
   1.255 +              distance = rep2;
   1.256 +            }
   1.257 +            else
   1.258 +            {
   1.259 +              UPDATE_1(prob);
   1.260 +              distance = rep3;
   1.261 +              rep3 = rep2;
   1.262 +            }
   1.263 +            rep2 = rep1;
   1.264 +          }
   1.265 +          rep1 = rep0;
   1.266 +          rep0 = distance;
   1.267 +        }
   1.268 +        state = state < kNumLitStates ? 8 : 11;
   1.269 +        prob = probs + RepLenCoder;
   1.270 +      }
   1.271 +      {
   1.272 +        unsigned limit, offset;
   1.273 +        CLzmaProb *probLen = prob + LenChoice;
   1.274 +        IF_BIT_0(probLen)
   1.275 +        {
   1.276 +          UPDATE_0(probLen);
   1.277 +          probLen = prob + LenLow + (posState << kLenNumLowBits);
   1.278 +          offset = 0;
   1.279 +          limit = (1 << kLenNumLowBits);
   1.280 +        }
   1.281 +        else
   1.282 +        {
   1.283 +          UPDATE_1(probLen);
   1.284 +          probLen = prob + LenChoice2;
   1.285 +          IF_BIT_0(probLen)
   1.286 +          {
   1.287 +            UPDATE_0(probLen);
   1.288 +            probLen = prob + LenMid + (posState << kLenNumMidBits);
   1.289 +            offset = kLenNumLowSymbols;
   1.290 +            limit = (1 << kLenNumMidBits);
   1.291 +          }
   1.292 +          else
   1.293 +          {
   1.294 +            UPDATE_1(probLen);
   1.295 +            probLen = prob + LenHigh;
   1.296 +            offset = kLenNumLowSymbols + kLenNumMidSymbols;
   1.297 +            limit = (1 << kLenNumHighBits);
   1.298 +          }
   1.299 +        }
   1.300 +        TREE_DECODE(probLen, limit, len);
   1.301 +        len += offset;
   1.302 +      }
   1.303 +
   1.304 +      if (state >= kNumStates)
   1.305 +      {
   1.306 +        UInt32 distance;
   1.307 +        prob = probs + PosSlot +
   1.308 +            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
   1.309 +        TREE_6_DECODE(prob, distance);
   1.310 +        if (distance >= kStartPosModelIndex)
   1.311 +        {
   1.312 +          unsigned posSlot = (unsigned)distance;
   1.313 +          int numDirectBits = (int)(((distance >> 1) - 1));
   1.314 +          distance = (2 | (distance & 1));
   1.315 +          if (posSlot < kEndPosModelIndex)
   1.316 +          {
   1.317 +            distance <<= numDirectBits;
   1.318 +            prob = probs + SpecPos + distance - posSlot - 1;
   1.319 +            {
   1.320 +              UInt32 mask = 1;
   1.321 +              unsigned i = 1;
   1.322 +              do
   1.323 +              {
   1.324 +                GET_BIT2(prob + i, i, ; , distance |= mask);
   1.325 +                mask <<= 1;
   1.326 +              }
   1.327 +              while (--numDirectBits != 0);
   1.328 +            }
   1.329 +          }
   1.330 +          else
   1.331 +          {
   1.332 +            numDirectBits -= kNumAlignBits;
   1.333 +            do
   1.334 +            {
   1.335 +              NORMALIZE
   1.336 +              range >>= 1;
   1.337 +              
   1.338 +              {
   1.339 +                UInt32 t;
   1.340 +                code -= range;
   1.341 +                t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
   1.342 +                distance = (distance << 1) + (t + 1);
   1.343 +                code += range & t;
   1.344 +              }
   1.345 +              /*
   1.346 +              distance <<= 1;
   1.347 +              if (code >= range)
   1.348 +              {
   1.349 +                code -= range;
   1.350 +                distance |= 1;
   1.351 +              }
   1.352 +              */
   1.353 +            }
   1.354 +            while (--numDirectBits != 0);
   1.355 +            prob = probs + Align;
   1.356 +            distance <<= kNumAlignBits;
   1.357 +            {
   1.358 +              unsigned i = 1;
   1.359 +              GET_BIT2(prob + i, i, ; , distance |= 1);
   1.360 +              GET_BIT2(prob + i, i, ; , distance |= 2);
   1.361 +              GET_BIT2(prob + i, i, ; , distance |= 4);
   1.362 +              GET_BIT2(prob + i, i, ; , distance |= 8);
   1.363 +            }
   1.364 +            if (distance == (UInt32)0xFFFFFFFF)
   1.365 +            {
   1.366 +              len += kMatchSpecLenStart;
   1.367 +              state -= kNumStates;
   1.368 +              break;
   1.369 +            }
   1.370 +          }
   1.371 +        }
   1.372 +        rep3 = rep2;
   1.373 +        rep2 = rep1;
   1.374 +        rep1 = rep0;
   1.375 +        rep0 = distance + 1;
   1.376 +        if (checkDicSize == 0)
   1.377 +        {
   1.378 +          if (distance >= processedPos)
   1.379 +            return SZ_ERROR_DATA;
   1.380 +        }
   1.381 +        else if (distance >= checkDicSize)
   1.382 +          return SZ_ERROR_DATA;
   1.383 +        state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
   1.384 +        /* state = kLiteralNextStates[state]; */
   1.385 +      }
   1.386 +
   1.387 +      len += kMatchMinLen;
   1.388 +
   1.389 +      if (limit == dicPos)
   1.390 +        return SZ_ERROR_DATA;
   1.391 +      {
   1.392 +        SizeT rem = limit - dicPos;
   1.393 +        unsigned curLen = ((rem < len) ? (unsigned)rem : len);
   1.394 +        SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
   1.395 +
   1.396 +        processedPos += curLen;
   1.397 +
   1.398 +        len -= curLen;
   1.399 +        if (pos + curLen <= dicBufSize)
   1.400 +        {
   1.401 +          Byte *dest = dic + dicPos;
   1.402 +          ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
   1.403 +          const Byte *lim = dest + curLen;
   1.404 +          dicPos += curLen;
   1.405 +          do
   1.406 +            *(dest) = (Byte)*(dest + src);
   1.407 +          while (++dest != lim);
   1.408 +        }
   1.409 +        else
   1.410 +        {
   1.411 +          do
   1.412 +          {
   1.413 +            dic[dicPos++] = dic[pos];
   1.414 +            if (++pos == dicBufSize)
   1.415 +              pos = 0;
   1.416 +          }
   1.417 +          while (--curLen != 0);
   1.418 +        }
   1.419 +      }
   1.420 +    }
   1.421 +  }
   1.422 +  while (dicPos < limit && buf < bufLimit);
   1.423 +  NORMALIZE;
   1.424 +  p->buf = buf;
   1.425 +  p->range = range;
   1.426 +  p->code = code;
   1.427 +  p->remainLen = len;
   1.428 +  p->dicPos = dicPos;
   1.429 +  p->processedPos = processedPos;
   1.430 +  p->reps[0] = rep0;
   1.431 +  p->reps[1] = rep1;
   1.432 +  p->reps[2] = rep2;
   1.433 +  p->reps[3] = rep3;
   1.434 +  p->state = state;
   1.435 +
   1.436 +  return SZ_OK;
   1.437 +}
   1.438 +
   1.439 +static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)
   1.440 +{
   1.441 +  if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
   1.442 +  {
   1.443 +    Byte *dic = p->dic;
   1.444 +    SizeT dicPos = p->dicPos;
   1.445 +    SizeT dicBufSize = p->dicBufSize;
   1.446 +    unsigned len = p->remainLen;
   1.447 +    UInt32 rep0 = p->reps[0];
   1.448 +    if (limit - dicPos < len)
   1.449 +      len = (unsigned)(limit - dicPos);
   1.450 +
   1.451 +    if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
   1.452 +      p->checkDicSize = p->prop.dicSize;
   1.453 +
   1.454 +    p->processedPos += len;
   1.455 +    p->remainLen -= len;
   1.456 +    while (len-- != 0)
   1.457 +    {
   1.458 +      dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
   1.459 +      dicPos++;
   1.460 +    }
   1.461 +    p->dicPos = dicPos;
   1.462 +  }
   1.463 +}
   1.464 +
   1.465 +static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
   1.466 +{
   1.467 +  do
   1.468 +  {
   1.469 +    SizeT limit2 = limit;
   1.470 +    if (p->checkDicSize == 0)
   1.471 +    {
   1.472 +      UInt32 rem = p->prop.dicSize - p->processedPos;
   1.473 +      if (limit - p->dicPos > rem)
   1.474 +        limit2 = p->dicPos + rem;
   1.475 +    }
   1.476 +    RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));
   1.477 +    if (p->processedPos >= p->prop.dicSize)
   1.478 +      p->checkDicSize = p->prop.dicSize;
   1.479 +    LzmaDec_WriteRem(p, limit);
   1.480 +  }
   1.481 +  while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
   1.482 +
   1.483 +  if (p->remainLen > kMatchSpecLenStart)
   1.484 +  {
   1.485 +    p->remainLen = kMatchSpecLenStart;
   1.486 +  }
   1.487 +  return 0;
   1.488 +}
   1.489 +
   1.490 +typedef enum
   1.491 +{
   1.492 +  DUMMY_ERROR, /* unexpected end of input stream */
   1.493 +  DUMMY_LIT,
   1.494 +  DUMMY_MATCH,
   1.495 +  DUMMY_REP
   1.496 +} ELzmaDummy;
   1.497 +
   1.498 +static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)
   1.499 +{
   1.500 +  UInt32 range = p->range;
   1.501 +  UInt32 code = p->code;
   1.502 +  const Byte *bufLimit = buf + inSize;
   1.503 +  CLzmaProb *probs = p->probs;
   1.504 +  unsigned state = p->state;
   1.505 +  ELzmaDummy res;
   1.506 +
   1.507 +  {
   1.508 +    CLzmaProb *prob;
   1.509 +    UInt32 bound;
   1.510 +    unsigned ttt;
   1.511 +    unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);
   1.512 +
   1.513 +    prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
   1.514 +    IF_BIT_0_CHECK(prob)
   1.515 +    {
   1.516 +      UPDATE_0_CHECK
   1.517 +
   1.518 +      /* if (bufLimit - buf >= 7) return DUMMY_LIT; */
   1.519 +
   1.520 +      prob = probs + Literal;
   1.521 +      if (p->checkDicSize != 0 || p->processedPos != 0)
   1.522 +        prob += (LZMA_LIT_SIZE *
   1.523 +          ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
   1.524 +          (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
   1.525 +
   1.526 +      if (state < kNumLitStates)
   1.527 +      {
   1.528 +        unsigned symbol = 1;
   1.529 +        do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);
   1.530 +      }
   1.531 +      else
   1.532 +      {
   1.533 +        unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
   1.534 +            ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)];
   1.535 +        unsigned offs = 0x100;
   1.536 +        unsigned symbol = 1;
   1.537 +        do
   1.538 +        {
   1.539 +          unsigned bit;
   1.540 +          CLzmaProb *probLit;
   1.541 +          matchByte <<= 1;
   1.542 +          bit = (matchByte & offs);
   1.543 +          probLit = prob + offs + bit + symbol;
   1.544 +          GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)
   1.545 +        }
   1.546 +        while (symbol < 0x100);
   1.547 +      }
   1.548 +      res = DUMMY_LIT;
   1.549 +    }
   1.550 +    else
   1.551 +    {
   1.552 +      unsigned len;
   1.553 +      UPDATE_1_CHECK;
   1.554 +
   1.555 +      prob = probs + IsRep + state;
   1.556 +      IF_BIT_0_CHECK(prob)
   1.557 +      {
   1.558 +        UPDATE_0_CHECK;
   1.559 +        state = 0;
   1.560 +        prob = probs + LenCoder;
   1.561 +        res = DUMMY_MATCH;
   1.562 +      }
   1.563 +      else
   1.564 +      {
   1.565 +        UPDATE_1_CHECK;
   1.566 +        res = DUMMY_REP;
   1.567 +        prob = probs + IsRepG0 + state;
   1.568 +        IF_BIT_0_CHECK(prob)
   1.569 +        {
   1.570 +          UPDATE_0_CHECK;
   1.571 +          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
   1.572 +          IF_BIT_0_CHECK(prob)
   1.573 +          {
   1.574 +            UPDATE_0_CHECK;
   1.575 +            NORMALIZE_CHECK;
   1.576 +            return DUMMY_REP;
   1.577 +          }
   1.578 +          else
   1.579 +          {
   1.580 +            UPDATE_1_CHECK;
   1.581 +          }
   1.582 +        }
   1.583 +        else
   1.584 +        {
   1.585 +          UPDATE_1_CHECK;
   1.586 +          prob = probs + IsRepG1 + state;
   1.587 +          IF_BIT_0_CHECK(prob)
   1.588 +          {
   1.589 +            UPDATE_0_CHECK;
   1.590 +          }
   1.591 +          else
   1.592 +          {
   1.593 +            UPDATE_1_CHECK;
   1.594 +            prob = probs + IsRepG2 + state;
   1.595 +            IF_BIT_0_CHECK(prob)
   1.596 +            {
   1.597 +              UPDATE_0_CHECK;
   1.598 +            }
   1.599 +            else
   1.600 +            {
   1.601 +              UPDATE_1_CHECK;
   1.602 +            }
   1.603 +          }
   1.604 +        }
   1.605 +        state = kNumStates;
   1.606 +        prob = probs + RepLenCoder;
   1.607 +      }
   1.608 +      {
   1.609 +        unsigned limit, offset;
   1.610 +        CLzmaProb *probLen = prob + LenChoice;
   1.611 +        IF_BIT_0_CHECK(probLen)
   1.612 +        {
   1.613 +          UPDATE_0_CHECK;
   1.614 +          probLen = prob + LenLow + (posState << kLenNumLowBits);
   1.615 +          offset = 0;
   1.616 +          limit = 1 << kLenNumLowBits;
   1.617 +        }
   1.618 +        else
   1.619 +        {
   1.620 +          UPDATE_1_CHECK;
   1.621 +          probLen = prob + LenChoice2;
   1.622 +          IF_BIT_0_CHECK(probLen)
   1.623 +          {
   1.624 +            UPDATE_0_CHECK;
   1.625 +            probLen = prob + LenMid + (posState << kLenNumMidBits);
   1.626 +            offset = kLenNumLowSymbols;
   1.627 +            limit = 1 << kLenNumMidBits;
   1.628 +          }
   1.629 +          else
   1.630 +          {
   1.631 +            UPDATE_1_CHECK;
   1.632 +            probLen = prob + LenHigh;
   1.633 +            offset = kLenNumLowSymbols + kLenNumMidSymbols;
   1.634 +            limit = 1 << kLenNumHighBits;
   1.635 +          }
   1.636 +        }
   1.637 +        TREE_DECODE_CHECK(probLen, limit, len);
   1.638 +        len += offset;
   1.639 +      }
   1.640 +
   1.641 +      if (state < 4)
   1.642 +      {
   1.643 +        unsigned posSlot;
   1.644 +        prob = probs + PosSlot +
   1.645 +            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
   1.646 +            kNumPosSlotBits);
   1.647 +        TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
   1.648 +        if (posSlot >= kStartPosModelIndex)
   1.649 +        {
   1.650 +          int numDirectBits = ((posSlot >> 1) - 1);
   1.651 +
   1.652 +          /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
   1.653 +
   1.654 +          if (posSlot < kEndPosModelIndex)
   1.655 +          {
   1.656 +            prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;
   1.657 +          }
   1.658 +          else
   1.659 +          {
   1.660 +            numDirectBits -= kNumAlignBits;
   1.661 +            do
   1.662 +            {
   1.663 +              NORMALIZE_CHECK
   1.664 +              range >>= 1;
   1.665 +              code -= range & (((code - range) >> 31) - 1);
   1.666 +              /* if (code >= range) code -= range; */
   1.667 +            }
   1.668 +            while (--numDirectBits != 0);
   1.669 +            prob = probs + Align;
   1.670 +            numDirectBits = kNumAlignBits;
   1.671 +          }
   1.672 +          {
   1.673 +            unsigned i = 1;
   1.674 +            do
   1.675 +            {
   1.676 +              GET_BIT_CHECK(prob + i, i);
   1.677 +            }
   1.678 +            while (--numDirectBits != 0);
   1.679 +          }
   1.680 +        }
   1.681 +      }
   1.682 +    }
   1.683 +  }
   1.684 +  NORMALIZE_CHECK;
   1.685 +  return res;
   1.686 +}
   1.687 +
   1.688 +
   1.689 +static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data)
   1.690 +{
   1.691 +  p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]);
   1.692 +  p->range = 0xFFFFFFFF;
   1.693 +  p->needFlush = 0;
   1.694 +}
   1.695 +
   1.696 +void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)
   1.697 +{
   1.698 +  p->needFlush = 1;
   1.699 +  p->remainLen = 0;
   1.700 +  p->tempBufSize = 0;
   1.701 +
   1.702 +  if (initDic)
   1.703 +  {
   1.704 +    p->processedPos = 0;
   1.705 +    p->checkDicSize = 0;
   1.706 +    p->needInitState = 1;
   1.707 +  }
   1.708 +  if (initState)
   1.709 +    p->needInitState = 1;
   1.710 +}
   1.711 +
   1.712 +void LzmaDec_Init(CLzmaDec *p)
   1.713 +{
   1.714 +  p->dicPos = 0;
   1.715 +  LzmaDec_InitDicAndState(p, True, True);
   1.716 +}
   1.717 +
   1.718 +static void LzmaDec_InitStateReal(CLzmaDec *p)
   1.719 +{
   1.720 +  UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
   1.721 +  UInt32 i;
   1.722 +  CLzmaProb *probs = p->probs;
   1.723 +  for (i = 0; i < numProbs; i++)
   1.724 +    probs[i] = kBitModelTotal >> 1;
   1.725 +  p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
   1.726 +  p->state = 0;
   1.727 +  p->needInitState = 0;
   1.728 +}
   1.729 +
   1.730 +SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,
   1.731 +    ELzmaFinishMode finishMode, ELzmaStatus *status)
   1.732 +{
   1.733 +  SizeT inSize = *srcLen;
   1.734 +  (*srcLen) = 0;
   1.735 +  LzmaDec_WriteRem(p, dicLimit);
   1.736 +  
   1.737 +  *status = LZMA_STATUS_NOT_SPECIFIED;
   1.738 +
   1.739 +  while (p->remainLen != kMatchSpecLenStart)
   1.740 +  {
   1.741 +      int checkEndMarkNow;
   1.742 +
   1.743 +      if (p->needFlush != 0)
   1.744 +      {
   1.745 +        for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
   1.746 +          p->tempBuf[p->tempBufSize++] = *src++;
   1.747 +        if (p->tempBufSize < RC_INIT_SIZE)
   1.748 +        {
   1.749 +          *status = LZMA_STATUS_NEEDS_MORE_INPUT;
   1.750 +          return SZ_OK;
   1.751 +        }
   1.752 +        if (p->tempBuf[0] != 0)
   1.753 +          return SZ_ERROR_DATA;
   1.754 +
   1.755 +        LzmaDec_InitRc(p, p->tempBuf);
   1.756 +        p->tempBufSize = 0;
   1.757 +      }
   1.758 +
   1.759 +      checkEndMarkNow = 0;
   1.760 +      if (p->dicPos >= dicLimit)
   1.761 +      {
   1.762 +        if (p->remainLen == 0 && p->code == 0)
   1.763 +        {
   1.764 +          *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
   1.765 +          return SZ_OK;
   1.766 +        }
   1.767 +        if (finishMode == LZMA_FINISH_ANY)
   1.768 +        {
   1.769 +          *status = LZMA_STATUS_NOT_FINISHED;
   1.770 +          return SZ_OK;
   1.771 +        }
   1.772 +        if (p->remainLen != 0)
   1.773 +        {
   1.774 +          *status = LZMA_STATUS_NOT_FINISHED;
   1.775 +          return SZ_ERROR_DATA;
   1.776 +        }
   1.777 +        checkEndMarkNow = 1;
   1.778 +      }
   1.779 +
   1.780 +      if (p->needInitState)
   1.781 +        LzmaDec_InitStateReal(p);
   1.782 +  
   1.783 +      if (p->tempBufSize == 0)
   1.784 +      {
   1.785 +        SizeT processed;
   1.786 +        const Byte *bufLimit;
   1.787 +        if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
   1.788 +        {
   1.789 +          int dummyRes = LzmaDec_TryDummy(p, src, inSize);
   1.790 +          if (dummyRes == DUMMY_ERROR)
   1.791 +          {
   1.792 +            memcpy(p->tempBuf, src, inSize);
   1.793 +            p->tempBufSize = (unsigned)inSize;
   1.794 +            (*srcLen) += inSize;
   1.795 +            *status = LZMA_STATUS_NEEDS_MORE_INPUT;
   1.796 +            return SZ_OK;
   1.797 +          }
   1.798 +          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
   1.799 +          {
   1.800 +            *status = LZMA_STATUS_NOT_FINISHED;
   1.801 +            return SZ_ERROR_DATA;
   1.802 +          }
   1.803 +          bufLimit = src;
   1.804 +        }
   1.805 +        else
   1.806 +          bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
   1.807 +        p->buf = src;
   1.808 +        if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
   1.809 +          return SZ_ERROR_DATA;
   1.810 +        processed = (SizeT)(p->buf - src);
   1.811 +        (*srcLen) += processed;
   1.812 +        src += processed;
   1.813 +        inSize -= processed;
   1.814 +      }
   1.815 +      else
   1.816 +      {
   1.817 +        unsigned rem = p->tempBufSize, lookAhead = 0;
   1.818 +        while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
   1.819 +          p->tempBuf[rem++] = src[lookAhead++];
   1.820 +        p->tempBufSize = rem;
   1.821 +        if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
   1.822 +        {
   1.823 +          int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
   1.824 +          if (dummyRes == DUMMY_ERROR)
   1.825 +          {
   1.826 +            (*srcLen) += lookAhead;
   1.827 +            *status = LZMA_STATUS_NEEDS_MORE_INPUT;
   1.828 +            return SZ_OK;
   1.829 +          }
   1.830 +          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
   1.831 +          {
   1.832 +            *status = LZMA_STATUS_NOT_FINISHED;
   1.833 +            return SZ_ERROR_DATA;
   1.834 +          }
   1.835 +        }
   1.836 +        p->buf = p->tempBuf;
   1.837 +        if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
   1.838 +          return SZ_ERROR_DATA;
   1.839 +        lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));
   1.840 +        (*srcLen) += lookAhead;
   1.841 +        src += lookAhead;
   1.842 +        inSize -= lookAhead;
   1.843 +        p->tempBufSize = 0;
   1.844 +      }
   1.845 +  }
   1.846 +  if (p->code == 0)
   1.847 +    *status = LZMA_STATUS_FINISHED_WITH_MARK;
   1.848 +  return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;
   1.849 +}
   1.850 +
   1.851 +SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
   1.852 +{
   1.853 +  SizeT outSize = *destLen;
   1.854 +  SizeT inSize = *srcLen;
   1.855 +  *srcLen = *destLen = 0;
   1.856 +  for (;;)
   1.857 +  {
   1.858 +    SizeT inSizeCur = inSize, outSizeCur, dicPos;
   1.859 +    ELzmaFinishMode curFinishMode;
   1.860 +    SRes res;
   1.861 +    if (p->dicPos == p->dicBufSize)
   1.862 +      p->dicPos = 0;
   1.863 +    dicPos = p->dicPos;
   1.864 +    if (outSize > p->dicBufSize - dicPos)
   1.865 +    {
   1.866 +      outSizeCur = p->dicBufSize;
   1.867 +      curFinishMode = LZMA_FINISH_ANY;
   1.868 +    }
   1.869 +    else
   1.870 +    {
   1.871 +      outSizeCur = dicPos + outSize;
   1.872 +      curFinishMode = finishMode;
   1.873 +    }
   1.874 +
   1.875 +    res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
   1.876 +    src += inSizeCur;
   1.877 +    inSize -= inSizeCur;
   1.878 +    *srcLen += inSizeCur;
   1.879 +    outSizeCur = p->dicPos - dicPos;
   1.880 +    memcpy(dest, p->dic + dicPos, outSizeCur);
   1.881 +    dest += outSizeCur;
   1.882 +    outSize -= outSizeCur;
   1.883 +    *destLen += outSizeCur;
   1.884 +    if (res != 0)
   1.885 +      return res;
   1.886 +    if (outSizeCur == 0 || outSize == 0)
   1.887 +      return SZ_OK;
   1.888 +  }
   1.889 +}
   1.890 +
   1.891 +void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc)
   1.892 +{
   1.893 +  alloc->Free(alloc, p->probs);
   1.894 +  p->probs = 0;
   1.895 +}
   1.896 +
   1.897 +static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)
   1.898 +{
   1.899 +  alloc->Free(alloc, p->dic);
   1.900 +  p->dic = 0;
   1.901 +}
   1.902 +
   1.903 +void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)
   1.904 +{
   1.905 +  LzmaDec_FreeProbs(p, alloc);
   1.906 +  LzmaDec_FreeDict(p, alloc);
   1.907 +}
   1.908 +
   1.909 +SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
   1.910 +{
   1.911 +  UInt32 dicSize;
   1.912 +  Byte d;
   1.913 +  
   1.914 +  if (size < LZMA_PROPS_SIZE)
   1.915 +    return SZ_ERROR_UNSUPPORTED;
   1.916 +  else
   1.917 +    dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
   1.918 + 
   1.919 +  if (dicSize < LZMA_DIC_MIN)
   1.920 +    dicSize = LZMA_DIC_MIN;
   1.921 +  p->dicSize = dicSize;
   1.922 +
   1.923 +  d = data[0];
   1.924 +  if (d >= (9 * 5 * 5))
   1.925 +    return SZ_ERROR_UNSUPPORTED;
   1.926 +
   1.927 +  p->lc = d % 9;
   1.928 +  d /= 9;
   1.929 +  p->pb = d / 5;
   1.930 +  p->lp = d % 5;
   1.931 +
   1.932 +  return SZ_OK;
   1.933 +}
   1.934 +
   1.935 +static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc)
   1.936 +{
   1.937 +  UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
   1.938 +  if (p->probs == 0 || numProbs != p->numProbs)
   1.939 +  {
   1.940 +    LzmaDec_FreeProbs(p, alloc);
   1.941 +    p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));
   1.942 +    p->numProbs = numProbs;
   1.943 +    if (p->probs == 0)
   1.944 +      return SZ_ERROR_MEM;
   1.945 +  }
   1.946 +  return SZ_OK;
   1.947 +}
   1.948 +
   1.949 +SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
   1.950 +{
   1.951 +  CLzmaProps propNew;
   1.952 +  RINOK(LzmaProps_Decode(&propNew, props, propsSize));
   1.953 +  RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
   1.954 +  p->prop = propNew;
   1.955 +  return SZ_OK;
   1.956 +}
   1.957 +
   1.958 +SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
   1.959 +{
   1.960 +  CLzmaProps propNew;
   1.961 +  SizeT dicBufSize;
   1.962 +  RINOK(LzmaProps_Decode(&propNew, props, propsSize));
   1.963 +  RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
   1.964 +  dicBufSize = propNew.dicSize;
   1.965 +  if (p->dic == 0 || dicBufSize != p->dicBufSize)
   1.966 +  {
   1.967 +    LzmaDec_FreeDict(p, alloc);
   1.968 +    p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);
   1.969 +    if (p->dic == 0)
   1.970 +    {
   1.971 +      LzmaDec_FreeProbs(p, alloc);
   1.972 +      return SZ_ERROR_MEM;
   1.973 +    }
   1.974 +  }
   1.975 +  p->dicBufSize = dicBufSize;
   1.976 +  p->prop = propNew;
   1.977 +  return SZ_OK;
   1.978 +}
   1.979 +
   1.980 +SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
   1.981 +    const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
   1.982 +    ELzmaStatus *status, ISzAlloc *alloc)
   1.983 +{
   1.984 +  CLzmaDec p;
   1.985 +  SRes res;
   1.986 +  SizeT inSize = *srcLen;
   1.987 +  SizeT outSize = *destLen;
   1.988 +  *srcLen = *destLen = 0;
   1.989 +  if (inSize < RC_INIT_SIZE)
   1.990 +    return SZ_ERROR_INPUT_EOF;
   1.991 +
   1.992 +  LzmaDec_Construct(&p);
   1.993 +  res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc);
   1.994 +  if (res != 0)
   1.995 +    return res;
   1.996 +  p.dic = dest;
   1.997 +  p.dicBufSize = outSize;
   1.998 +
   1.999 +  LzmaDec_Init(&p);
  1.1000 +  
  1.1001 +  *srcLen = inSize;
  1.1002 +  res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
  1.1003 +
  1.1004 +  if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
  1.1005 +    res = SZ_ERROR_INPUT_EOF;
  1.1006 +
  1.1007 +  (*destLen) = p.dicPos;
  1.1008 +  LzmaDec_FreeProbs(&p, alloc);
  1.1009 +  return res;
  1.1010 +}