third_party/lzma_sdk/LzmaDec.c

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