installer/lzma/LzmaDecode.c

   1 /*
   2   LzmaDecode.c
   3   LZMA Decoder (optimized for Speed version)
   4
   5   LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01)
   6   http://www.7-zip.org/
   7
   8   LZMA SDK is licensed under two licenses:
   9   1) GNU Lesser General Public License (GNU LGPL)
  10   2) Common Public License (CPL)
  11   It means that you can select one of these two licenses and
  12   follow rules of that license.
  13
  14   SPECIAL EXCEPTION:
  15   Igor Pavlov, as the author of this Code, expressly permits you to
  16   statically or dynamically link your Code (or bind by name) to the
  17   interfaces of this file without subjecting your linked Code to the
  18   terms of the CPL or GNU LGPL. Any modifications or additions
  19   to this file, however, are subject to the LGPL or CPL terms.
  20 */
  21
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24
  25 #include "LzmaDecode.h"
  26
  27 #define kNumTopBits 24
  28 #define kTopValue ((UInt32)1 << kNumTopBits)
  29
  30 #define kNumBitModelTotalBits 11
  31 #define kBitModelTotal (1 << kNumBitModelTotalBits)
  32 #define kNumMoveBits 5
  33
  34 #define RC_READ_BYTE (*Buffer++)
  35
  36 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
  37   { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
  38
  39 #ifdef _LZMA_IN_CB
  40
  41 #define RC_TEST { if (Buffer == BufferLim) \
  42   { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
  43   BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
  44
  45 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
  46
  47 #else
  48
  49 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
  50
  51 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
  52
  53 #endif
  54
  55 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
  56
  57 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
  58 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
  59 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
  60
  61 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
  62   { UpdateBit0(p); mi <<= 1; A0; } else \
  63   { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
  64
  65 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
  66
  67 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
  68   { int i = numLevels; res = 1; \
  69   do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
  70   res -= (1 << numLevels); }
  71
  72
  73 #define kNumPosBitsMax 4
  74 #define kNumPosStatesMax (1 << kNumPosBitsMax)
  75
  76 #define kLenNumLowBits 3
  77 #define kLenNumLowSymbols (1 << kLenNumLowBits)
  78 #define kLenNumMidBits 3
  79 #define kLenNumMidSymbols (1 << kLenNumMidBits)
  80 #define kLenNumHighBits 8
  81 #define kLenNumHighSymbols (1 << kLenNumHighBits)
  82
  83 #define LenChoice 0
  84 #define LenChoice2 (LenChoice + 1)
  85 #define LenLow (LenChoice2 + 1)
  86 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
  87 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
  88 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
  89
  90
  91 #define kNumStates 12
  92 #define kNumLitStates 7
  93
  94 #define kStartPosModelIndex 4
  95 #define kEndPosModelIndex 14
  96 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
  97
  98 #define kNumPosSlotBits 6
  99 #define kNumLenToPosStates 4
 100
 101 #define kNumAlignBits 4
 102 #define kAlignTableSize (1 << kNumAlignBits)
 103
 104 #define kMatchMinLen 2
 105
 106 #define IsMatch 0
 107 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
 108 #define IsRepG0 (IsRep + kNumStates)
 109 #define IsRepG1 (IsRepG0 + kNumStates)
 110 #define IsRepG2 (IsRepG1 + kNumStates)
 111 #define IsRep0Long (IsRepG2 + kNumStates)
 112 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
 113 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
 114 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
 115 #define LenCoder (Align + kAlignTableSize)
 116 #define RepLenCoder (LenCoder + kNumLenProbs)
 117 #define Literal (RepLenCoder + kNumLenProbs)
 118
 119 #if Literal != LZMA_BASE_SIZE
 120 StopCompilingDueBUG
 121 #endif
 122
 123 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
 124 {
 125   unsigned char prop0;
 126   if (size < LZMA_PROPERTIES_SIZE)
 127     return LZMA_RESULT_DATA_ERROR;
 128   prop0 = propsData[0];
 129   if (prop0 >= (9 * 5 * 5))
 130     return LZMA_RESULT_DATA_ERROR;
 131   {
 132     for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
 133     for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
 134     propsRes->lc = prop0;
 135     /*
 136     unsigned char remainder = (unsigned char)(prop0 / 9);
 137     propsRes->lc = prop0 % 9;
 138     propsRes->pb = remainder / 5;
 139     propsRes->lp = remainder % 5;
 140     */
 141   }
 142
 143   #ifdef _LZMA_OUT_READ
 144   {
 145     int i;
 146     propsRes->DictionarySize = 0;
 147     for (i = 0; i < 4; i++)
 148       propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
 149     if (propsRes->DictionarySize == 0)
 150       propsRes->DictionarySize = 1;
 151   }
 152   #endif
 153   return LZMA_RESULT_OK;
 154 }
 155
 156 #define kLzmaStreamWasFinishedId (-1)
 157
 158 int LzmaDecode(CLzmaDecoderState *vs,
 159     #ifdef _LZMA_IN_CB
 160     ILzmaInCallback *InCallback,
 161     #else
 162     const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
 163     #endif
 164     unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
 165 {
 166   CProb *p = vs->Probs;
 167   SizeT nowPos = 0;
 168   Byte previousByte = 0;
 169   UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
 170   UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
 171   int lc = vs->Properties.lc;
 172
 173   #ifdef _LZMA_OUT_READ
 174
 175   UInt32 Range = vs->Range;
 176   UInt32 Code = vs->Code;
 177   #ifdef _LZMA_IN_CB
 178   const Byte *Buffer = vs->Buffer;
 179   const Byte *BufferLim = vs->BufferLim;
 180   #else
 181   const Byte *Buffer = inStream;
 182   const Byte *BufferLim = inStream + inSize;
 183   #endif
 184   int state = vs->State;
 185   UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
 186   int len = vs->RemainLen;
 187   UInt32 globalPos = vs->GlobalPos;
 188   UInt32 distanceLimit = vs->DistanceLimit;
 189
 190   Byte *dictionary = vs->Dictionary;
 191   UInt32 dictionarySize = vs->Properties.DictionarySize;
 192   UInt32 dictionaryPos = vs->DictionaryPos;
 193
 194   Byte tempDictionary[4];
 195
 196   #ifndef _LZMA_IN_CB
 197   *inSizeProcessed = 0;
 198   #endif
 199   *outSizeProcessed = 0;
 200   if (len == kLzmaStreamWasFinishedId)
 201     return LZMA_RESULT_OK;
 202
 203   if (dictionarySize == 0)
 204   {
 205     dictionary = tempDictionary;
 206     dictionarySize = 1;
 207     tempDictionary[0] = vs->TempDictionary[0];
 208   }
 209
 210   if (len == kLzmaNeedInitId)
 211   {
 212     {
 213       UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 214       UInt32 i;
 215       for (i = 0; i < numProbs; i++)
 216         p[i] = kBitModelTotal >> 1;
 217       rep0 = rep1 = rep2 = rep3 = 1;
 218       state = 0;
 219       globalPos = 0;
 220       distanceLimit = 0;
 221       dictionaryPos = 0;
 222       dictionary[dictionarySize - 1] = 0;
 223       #ifdef _LZMA_IN_CB
 224       RC_INIT;
 225       #else
 226       RC_INIT(inStream, inSize);
 227       #endif
 228     }
 229     len = 0;
 230   }
 231   while(len != 0 && nowPos < outSize)
 232   {
 233     UInt32 pos = dictionaryPos - rep0;
 234     if (pos >= dictionarySize)
 235       pos += dictionarySize;
 236     outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
 237     if (++dictionaryPos == dictionarySize)
 238       dictionaryPos = 0;
 239     len--;
 240   }
 241   if (dictionaryPos == 0)
 242     previousByte = dictionary[dictionarySize - 1];
 243   else
 244     previousByte = dictionary[dictionaryPos - 1];
 245
 246   #else /* if !_LZMA_OUT_READ */
 247
 248   int state = 0;
 249   UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
 250   int len = 0;
 251   const Byte *Buffer;
 252   const Byte *BufferLim;
 253   UInt32 Range;
 254   UInt32 Code;
 255
 256   #ifndef _LZMA_IN_CB
 257   *inSizeProcessed = 0;
 258   #endif
 259   *outSizeProcessed = 0;
 260
 261   {
 262     UInt32 i;
 263     UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
 264     for (i = 0; i < numProbs; i++)
 265       p[i] = kBitModelTotal >> 1;
 266   }
 267
 268   #ifdef _LZMA_IN_CB
 269   RC_INIT;
 270   #else
 271   RC_INIT(inStream, inSize);
 272   #endif
 273
 274   #endif /* _LZMA_OUT_READ */
 275
 276   while(nowPos < outSize)
 277   {
 278     CProb *prob;
 279     UInt32 bound;
 280     int posState = (int)(
 281         (nowPos
 282         #ifdef _LZMA_OUT_READ
 283         + globalPos
 284         #endif
 285         )
 286         & posStateMask);
 287
 288     prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
 289     IfBit0(prob)
 290     {
 291       int symbol = 1;
 292       UpdateBit0(prob)
 293       prob = p + Literal + (LZMA_LIT_SIZE *
 294         (((
 295         (nowPos
 296         #ifdef _LZMA_OUT_READ
 297         + globalPos
 298         #endif
 299         )
 300         & literalPosMask) << lc) + (previousByte >> (8 - lc))));
 301
 302       if (state >= kNumLitStates)
 303       {
 304         int matchByte;
 305         #ifdef _LZMA_OUT_READ
 306         UInt32 pos = dictionaryPos - rep0;
 307         if (pos >= dictionarySize)
 308           pos += dictionarySize;
 309         matchByte = dictionary[pos];
 310         #else
 311         matchByte = outStream[nowPos - rep0];
 312         #endif
 313         do
 314         {
 315           int bit;
 316           CProb *probLit;
 317           matchByte <<= 1;
 318           bit = (matchByte & 0x100);
 319           probLit = prob + 0x100 + bit + symbol;
 320           RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
 321         }
 322         while (symbol < 0x100);
 323       }
 324       while (symbol < 0x100)
 325       {
 326         CProb *probLit = prob + symbol;
 327         RC_GET_BIT(probLit, symbol)
 328       }
 329       previousByte = (Byte)symbol;
 330
 331       outStream[nowPos++] = previousByte;
 332       #ifdef _LZMA_OUT_READ
 333       if (distanceLimit < dictionarySize)
 334         distanceLimit++;
 335
 336       dictionary[dictionaryPos] = previousByte;
 337       if (++dictionaryPos == dictionarySize)
 338         dictionaryPos = 0;
 339       #endif
 340       if (state < 4) state = 0;
 341       else if (state < 10) state -= 3;
 342       else state -= 6;
 343     }
 344     else
 345     {
 346       UpdateBit1(prob);
 347       prob = p + IsRep + state;
 348       IfBit0(prob)
 349       {
 350         UpdateBit0(prob);
 351         rep3 = rep2;
 352         rep2 = rep1;
 353         rep1 = rep0;
 354         state = state < kNumLitStates ? 0 : 3;
 355         prob = p + LenCoder;
 356       }
 357       else
 358       {
 359         UpdateBit1(prob);
 360         prob = p + IsRepG0 + state;
 361         IfBit0(prob)
 362         {
 363           UpdateBit0(prob);
 364           prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
 365           IfBit0(prob)
 366           {
 367             #ifdef _LZMA_OUT_READ
 368             UInt32 pos;
 369             #endif
 370             UpdateBit0(prob);
 371
 372             #ifdef _LZMA_OUT_READ
 373             if (distanceLimit == 0)
 374             #else
 375             if (nowPos == 0)
 376             #endif
 377             {
 378               printf("distanceLimit == 0\n");
 379               return LZMA_RESULT_DATA_ERROR;
 380             }
 381
 382             state = state < kNumLitStates ? 9 : 11;
 383             #ifdef _LZMA_OUT_READ
 384             pos = dictionaryPos - rep0;
 385             if (pos >= dictionarySize)
 386               pos += dictionarySize;
 387             previousByte = dictionary[pos];
 388             dictionary[dictionaryPos] = previousByte;
 389             if (++dictionaryPos == dictionarySize)
 390               dictionaryPos = 0;
 391             #else
 392             previousByte = outStream[nowPos - rep0];
 393             #endif
 394             outStream[nowPos++] = previousByte;
 395             #ifdef _LZMA_OUT_READ
 396             if (distanceLimit < dictionarySize)
 397               distanceLimit++;
 398             #endif
 399
 400             continue;
 401           }
 402           else
 403           {
 404             UpdateBit1(prob);
 405           }
 406         }
 407         else
 408         {
 409           UInt32 distance;
 410           UpdateBit1(prob);
 411           prob = p + IsRepG1 + state;
 412           IfBit0(prob)
 413           {
 414             UpdateBit0(prob);
 415             distance = rep1;
 416           }
 417           else
 418           {
 419             UpdateBit1(prob);
 420             prob = p + IsRepG2 + state;
 421             IfBit0(prob)
 422             {
 423               UpdateBit0(prob);
 424               distance = rep2;
 425             }
 426             else
 427             {
 428               UpdateBit1(prob);
 429               distance = rep3;
 430               rep3 = rep2;
 431             }
 432             rep2 = rep1;
 433           }
 434           rep1 = rep0;
 435           rep0 = distance;
 436         }
 437         state = state < kNumLitStates ? 8 : 11;
 438         prob = p + RepLenCoder;
 439       }
 440       {
 441         int numBits, offset;
 442         CProb *probLen = prob + LenChoice;
 443         IfBit0(probLen)
 444         {
 445           UpdateBit0(probLen);
 446           probLen = prob + LenLow + (posState << kLenNumLowBits);
 447           offset = 0;
 448           numBits = kLenNumLowBits;
 449         }
 450         else
 451         {
 452           UpdateBit1(probLen);
 453           probLen = prob + LenChoice2;
 454           IfBit0(probLen)
 455           {
 456             UpdateBit0(probLen);
 457             probLen = prob + LenMid + (posState << kLenNumMidBits);
 458             offset = kLenNumLowSymbols;
 459             numBits = kLenNumMidBits;
 460           }
 461           else
 462           {
 463             UpdateBit1(probLen);
 464             probLen = prob + LenHigh;
 465             offset = kLenNumLowSymbols + kLenNumMidSymbols;
 466             numBits = kLenNumHighBits;
 467           }
 468         }
 469         RangeDecoderBitTreeDecode(probLen, numBits, len);
 470         len += offset;
 471       }
 472
 473       if (state < 4)
 474       {
 475         int posSlot;
 476         state += kNumLitStates;
 477         prob = p + PosSlot +
 478             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
 479             kNumPosSlotBits);
 480         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
 481         if (posSlot >= kStartPosModelIndex)
 482         {
 483           int numDirectBits = ((posSlot >> 1) - 1);
 484           rep0 = (2 | ((UInt32)posSlot & 1));
 485           if (posSlot < kEndPosModelIndex)
 486           {
 487             rep0 <<= numDirectBits;
 488             prob = p + SpecPos + rep0 - posSlot - 1;
 489           }
 490           else
 491           {
 492             numDirectBits -= kNumAlignBits;
 493             do
 494             {
 495               RC_NORMALIZE
 496               Range >>= 1;
 497               rep0 <<= 1;
 498               if (Code >= Range)
 499               {
 500                 Code -= Range;
 501                 rep0 |= 1;
 502               }
 503             }
 504             while (--numDirectBits != 0);
 505             prob = p + Align;
 506             rep0 <<= kNumAlignBits;
 507             numDirectBits = kNumAlignBits;
 508           }
 509           {
 510             int i = 1;
 511             int mi = 1;
 512             do
 513             {
 514               CProb *prob3 = prob + mi;
 515               RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
 516               i <<= 1;
 517             }
 518             while(--numDirectBits != 0);
 519           }
 520         }
 521         else
 522           rep0 = posSlot;
 523         if (++rep0 == (UInt32)(0))
 524         {
 525           /* it's for stream version */
 526           len = kLzmaStreamWasFinishedId;
 527           break;
 528         }
 529       }
 530
 531       len += kMatchMinLen;
 532       #ifdef _LZMA_OUT_READ
 533       if (rep0 > distanceLimit)
 534       #else
 535       if (rep0 > nowPos)
 536       #endif
 537       {
 538         printf("rep0 %d > distanceLimit %d\n", rep0, distanceLimit);
 539         return LZMA_RESULT_DATA_ERROR;
 540       }
 541
 542       #ifdef _LZMA_OUT_READ
 543       if (dictionarySize - distanceLimit > (UInt32)len)
 544         distanceLimit += len;
 545       else
 546         distanceLimit = dictionarySize;
 547       #endif
 548
 549       do
 550       {
 551         #ifdef _LZMA_OUT_READ
 552         UInt32 pos = dictionaryPos - rep0;
 553         if (pos >= dictionarySize)
 554           pos += dictionarySize;
 555         previousByte = dictionary[pos];
 556         dictionary[dictionaryPos] = previousByte;
 557         if (++dictionaryPos == dictionarySize)
 558           dictionaryPos = 0;
 559         #else
 560         previousByte = outStream[nowPos - rep0];
 561         #endif
 562         len--;
 563         outStream[nowPos++] = previousByte;
 564       }
 565       while(len != 0 && nowPos < outSize);
 566     }
 567   }
 568   RC_NORMALIZE;
 569
 570   #ifdef _LZMA_OUT_READ
 571   vs->Range = Range;
 572   vs->Code = Code;
 573   vs->DictionaryPos = dictionaryPos;
 574   vs->GlobalPos = globalPos + (UInt32)nowPos;
 575   vs->DistanceLimit = distanceLimit;
 576   vs->Reps[0] = rep0;
 577   vs->Reps[1] = rep1;
 578   vs->Reps[2] = rep2;
 579   vs->Reps[3] = rep3;
 580   vs->State = state;
 581   vs->RemainLen = len;
 582   vs->TempDictionary[0] = tempDictionary[0];
 583   #endif
 584
 585   #ifdef _LZMA_IN_CB
 586   vs->Buffer = Buffer;
 587   vs->BufferLim = BufferLim;
 588   #else
 589   *inSizeProcessed = (SizeT)(Buffer - inStream);
 590   #endif
 591   *outSizeProcessed = nowPos;
 592   return LZMA_RESULT_OK;
 593 }