lib/lzma/LzmaDec.c

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