lib/LzmaDec.c

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