lib/lzma/LzmaDec.c

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