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