BaseTools/Source/C/LzmaCompress/Sdk/C/LzmaDec.c

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