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