IntelFrameworkModulePkg/Library/LzmaCustomDecompressLib/Sdk/C/LzmaDec.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<BR>
   9   All rights reserved. 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             *(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