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 "LzmaDecode.h"

    23 

    24 #define kNumTopBits 24

    25 #define kTopValue ((UInt32)1 << kNumTopBits)

    26 

    27 #define kNumBitModelTotalBits 11

    28 #define kBitModelTotal (1 << kNumBitModelTotalBits)

    29 #define kNumMoveBits 5

    30 

    31 #define RC_READ_BYTE (*Buffer++)

    32 

    33 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \

    34   { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}

    35 

    36 #ifdef _LZMA_IN_CB

    37 

    38 #define RC_TEST { if (Buffer == BufferLim) \

    39   { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \

    40   BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}

    41 

    42 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2

    43 

    44 #else

    45 

    46 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }

    47 

    48 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2

    49  

    50 #endif

    51 

    52 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }

    53 

    54 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)

    55 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;

    56 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;

    57 

    58 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \

    59   { UpdateBit0(p); mi <<= 1; A0; } else \

    60   { UpdateBit1(p); mi = (mi + mi) + 1; A1; } 

    61   

    62 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)               

    63 

    64 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \

    65   { int i = numLevels; res = 1; \

    66   do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \

    67   res -= (1 << numLevels); }

    68 

    69 

    70 #define kNumPosBitsMax 4

    71 #define kNumPosStatesMax (1 << kNumPosBitsMax)

    72 

    73 #define kLenNumLowBits 3

    74 #define kLenNumLowSymbols (1 << kLenNumLowBits)

    75 #define kLenNumMidBits 3

    76 #define kLenNumMidSymbols (1 << kLenNumMidBits)

    77 #define kLenNumHighBits 8

    78 #define kLenNumHighSymbols (1 << kLenNumHighBits)

    79 

    80 #define LenChoice 0

    81 #define LenChoice2 (LenChoice + 1)

    82 #define LenLow (LenChoice2 + 1)

    83 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))

    84 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))

    85 #define kNumLenProbs (LenHigh + kLenNumHighSymbols) 

    86 

    87 

    88 #define kNumStates 12

    89 #define kNumLitStates 7

    90 

    91 #define kStartPosModelIndex 4

    92 #define kEndPosModelIndex 14

    93 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))

    94 

    95 #define kNumPosSlotBits 6

    96 #define kNumLenToPosStates 4

    97 

    98 #define kNumAlignBits 4

    99 #define kAlignTableSize (1 << kNumAlignBits)

   100 

   101 #define kMatchMinLen 2

   102 

   103 #define IsMatch 0

   104 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))

   105 #define IsRepG0 (IsRep + kNumStates)

   106 #define IsRepG1 (IsRepG0 + kNumStates)

   107 #define IsRepG2 (IsRepG1 + kNumStates)

   108 #define IsRep0Long (IsRepG2 + kNumStates)

   109 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))

   110 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))

   111 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)

   112 #define LenCoder (Align + kAlignTableSize)

   113 #define RepLenCoder (LenCoder + kNumLenProbs)

   114 #define Literal (RepLenCoder + kNumLenProbs)

   115 

   116 #if Literal != LZMA_BASE_SIZE

   117 StopCompilingDueBUG

   118 #endif

   119 

   120 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)

   121 {

   122   unsigned char prop0;

   123   if (size < LZMA_PROPERTIES_SIZE)

   124     return LZMA_RESULT_DATA_ERROR;

   125   prop0 = propsData[0];

   126   if (prop0 >= (9 * 5 * 5))

   127     return LZMA_RESULT_DATA_ERROR;

   128   {

   129     for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));

   130     for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);

   131     propsRes->lc = prop0;

   132     /*

   133     unsigned char remainder = (unsigned char)(prop0 / 9);

   134     propsRes->lc = prop0 % 9;

   135     propsRes->pb = remainder / 5;

   136     propsRes->lp = remainder % 5;

   137     */

   138   }

   139 

   140   #ifdef _LZMA_OUT_READ

   141   {

   142     int i;

   143     propsRes->DictionarySize = 0;

   144     for (i = 0; i < 4; i++)

   145       propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);

   146     if (propsRes->DictionarySize == 0)

   147       propsRes->DictionarySize = 1;

   148   }

   149   #endif

   150   return LZMA_RESULT_OK;

   151 }

   152 

   153 #define kLzmaStreamWasFinishedId (-1)

   154 

   155 int LzmaDecode(CLzmaDecoderState *vs,

   156     #ifdef _LZMA_IN_CB

   157     ILzmaInCallback *InCallback,

   158     #else

   159     const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,

   160     #endif

   161     unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)

   162 {

   163   CProb *p = vs->Probs;

   164   SizeT nowPos = 0;

   165   Byte previousByte = 0;

   166   UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;

   167   UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;

   168   int lc = vs->Properties.lc;

   169 

   170   #ifdef _LZMA_OUT_READ

   171   

   172   UInt32 Range = vs->Range;

   173   UInt32 Code = vs->Code;

   174   #ifdef _LZMA_IN_CB

   175   const Byte *Buffer = vs->Buffer;

   176   const Byte *BufferLim = vs->BufferLim;

   177   #else

   178   const Byte *Buffer = inStream;

   179   const Byte *BufferLim = inStream + inSize;

   180   #endif

   181   int state = vs->State;

   182   UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];

   183   int len = vs->RemainLen;

   184   UInt32 globalPos = vs->GlobalPos;

   185   UInt32 distanceLimit = vs->DistanceLimit;

   186 

   187   Byte *dictionary = vs->Dictionary;

   188   UInt32 dictionarySize = vs->Properties.DictionarySize;

   189   UInt32 dictionaryPos = vs->DictionaryPos;

   190 

   191   Byte tempDictionary[4];

   192 

   193   #ifndef _LZMA_IN_CB

   194   *inSizeProcessed = 0;

   195   #endif

   196   *outSizeProcessed = 0;

   197   if (len == kLzmaStreamWasFinishedId)

   198     return LZMA_RESULT_OK;

   199 

   200   if (dictionarySize == 0)

   201   {

   202     dictionary = tempDictionary;

   203     dictionarySize = 1;

   204     tempDictionary[0] = vs->TempDictionary[0];

   205   }

   206 

   207   if (len == kLzmaNeedInitId)

   208   {

   209     {

   210       UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));

   211       UInt32 i;

   212       for (i = 0; i < numProbs; i++)

   213         p[i] = kBitModelTotal >> 1; 

   214       rep0 = rep1 = rep2 = rep3 = 1;

   215       state = 0;

   216       globalPos = 0;

   217       distanceLimit = 0;

   218       dictionaryPos = 0;

   219       dictionary[dictionarySize - 1] = 0;

   220       #ifdef _LZMA_IN_CB

   221       RC_INIT;

   222       #else

   223       RC_INIT(inStream, inSize);

   224       #endif

   225     }

   226     len = 0;

   227   }

   228   while(len != 0 && nowPos < outSize)

   229   {

   230     UInt32 pos = dictionaryPos - rep0;

   231     if (pos >= dictionarySize)

   232       pos += dictionarySize;

   233     outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];

   234     if (++dictionaryPos == dictionarySize)

   235       dictionaryPos = 0;

   236     len--;

   237   }

   238   if (dictionaryPos == 0)

   239     previousByte = dictionary[dictionarySize - 1];

   240   else

   241     previousByte = dictionary[dictionaryPos - 1];

   242 

   243   #else /* if !_LZMA_OUT_READ */

   244 

   245   int state = 0;

   246   UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;

   247   int len = 0;

   248   const Byte *Buffer;

   249   const Byte *BufferLim;

   250   UInt32 Range;

   251   UInt32 Code;

   252 

   253   #ifndef _LZMA_IN_CB

   254   *inSizeProcessed = 0;

   255   #endif

   256   *outSizeProcessed = 0;

   257 

   258   {

   259     UInt32 i;

   260     UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));

   261     for (i = 0; i < numProbs; i++)

   262       p[i] = kBitModelTotal >> 1;

   263   }

   264   

   265   #ifdef _LZMA_IN_CB

   266   RC_INIT;

   267   #else

   268   RC_INIT(inStream, inSize);

   269   #endif

   270 

   271   #endif /* _LZMA_OUT_READ */

   272 

   273   while(nowPos < outSize)

   274   {

   275     CProb *prob;

   276     UInt32 bound;

   277     int posState = (int)(

   278         (nowPos 

   279         #ifdef _LZMA_OUT_READ

   280         + globalPos

   281         #endif

   282         )

   283         & posStateMask);

   284 

   285     prob = p + IsMatch + (state << kNumPosBitsMax) + posState;

   286     IfBit0(prob)

   287     {

   288       int symbol = 1;

   289       UpdateBit0(prob)

   290       prob = p + Literal + (LZMA_LIT_SIZE * 

   291         (((

   292         (nowPos 

   293         #ifdef _LZMA_OUT_READ

   294         + globalPos

   295         #endif

   296         )

   297         & literalPosMask) << lc) + (previousByte >> (8 - lc))));

   298 

   299       if (state >= kNumLitStates)

   300       {

   301         int matchByte;

   302         #ifdef _LZMA_OUT_READ

   303         UInt32 pos = dictionaryPos - rep0;

   304         if (pos >= dictionarySize)

   305           pos += dictionarySize;

   306         matchByte = dictionary[pos];

   307         #else

   308         matchByte = outStream[nowPos - rep0];

   309         #endif

   310         do

   311         {

   312           int bit;

   313           CProb *probLit;

   314           matchByte <<= 1;

   315           bit = (matchByte & 0x100);

   316           probLit = prob + 0x100 + bit + symbol;

   317           RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)

   318         }

   319         while (symbol < 0x100);

   320       }

   321       while (symbol < 0x100)

   322       {

   323         CProb *probLit = prob + symbol;

   324         RC_GET_BIT(probLit, symbol)

   325       }

   326       previousByte = (Byte)symbol;

   327 

   328       outStream[nowPos++] = previousByte;

   329       #ifdef _LZMA_OUT_READ

   330       if (distanceLimit < dictionarySize)

   331         distanceLimit++;

   332 

   333       dictionary[dictionaryPos] = previousByte;

   334       if (++dictionaryPos == dictionarySize)

   335         dictionaryPos = 0;

   336       #endif

   337       if (state < 4) state = 0;

   338       else if (state < 10) state -= 3;

   339       else state -= 6;

   340     }

   341     else             

   342     {

   343       UpdateBit1(prob);

   344       prob = p + IsRep + state;

   345       IfBit0(prob)

   346       {

   347         UpdateBit0(prob);

   348         rep3 = rep2;

   349         rep2 = rep1;

   350         rep1 = rep0;

   351         state = state < kNumLitStates ? 0 : 3;

   352         prob = p + LenCoder;

   353       }

   354       else

   355       {

   356         UpdateBit1(prob);

   357         prob = p + IsRepG0 + state;

   358         IfBit0(prob)

   359         {

   360           UpdateBit0(prob);

   361           prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;

   362           IfBit0(prob)

   363           {

   364             #ifdef _LZMA_OUT_READ

   365             UInt32 pos;

   366             #endif

   367             UpdateBit0(prob);

   368             

   369             #ifdef _LZMA_OUT_READ

   370             if (distanceLimit == 0)

   371             #else

   372             if (nowPos == 0)

   373             #endif

   374               return LZMA_RESULT_DATA_ERROR;

   375             

   376             state = state < kNumLitStates ? 9 : 11;

   377             #ifdef _LZMA_OUT_READ

   378             pos = dictionaryPos - rep0;

   379             if (pos >= dictionarySize)

   380               pos += dictionarySize;

   381             previousByte = dictionary[pos];

   382             dictionary[dictionaryPos] = previousByte;

   383             if (++dictionaryPos == dictionarySize)

   384               dictionaryPos = 0;

   385             #else

   386             previousByte = outStream[nowPos - rep0];

   387             #endif

   388             outStream[nowPos++] = previousByte;

   389             #ifdef _LZMA_OUT_READ

   390             if (distanceLimit < dictionarySize)

   391               distanceLimit++;

   392             #endif

   393 

   394             continue;

   395           }

   396           else

   397           {

   398             UpdateBit1(prob);

   399           }

   400         }

   401         else

   402         {

   403           UInt32 distance;

   404           UpdateBit1(prob);

   405           prob = p + IsRepG1 + state;

   406           IfBit0(prob)

   407           {

   408             UpdateBit0(prob);

   409             distance = rep1;

   410           }

   411           else 

   412           {

   413             UpdateBit1(prob);

   414             prob = p + IsRepG2 + state;

   415             IfBit0(prob)

   416             {

   417               UpdateBit0(prob);

   418               distance = rep2;

   419             }

   420             else

   421             {

   422               UpdateBit1(prob);

   423               distance = rep3;

   424               rep3 = rep2;

   425             }

   426             rep2 = rep1;

   427           }

   428           rep1 = rep0;

   429           rep0 = distance;

   430         }

   431         state = state < kNumLitStates ? 8 : 11;

   432         prob = p + RepLenCoder;

   433       }

   434       {

   435         int numBits, offset;

   436         CProb *probLen = prob + LenChoice;

   437         IfBit0(probLen)

   438         {

   439           UpdateBit0(probLen);

   440           probLen = prob + LenLow + (posState << kLenNumLowBits);

   441           offset = 0;

   442           numBits = kLenNumLowBits;

   443         }

   444         else

   445         {

   446           UpdateBit1(probLen);

   447           probLen = prob + LenChoice2;

   448           IfBit0(probLen)

   449           {

   450             UpdateBit0(probLen);

   451             probLen = prob + LenMid + (posState << kLenNumMidBits);

   452             offset = kLenNumLowSymbols;

   453             numBits = kLenNumMidBits;

   454           }

   455           else

   456           {

   457             UpdateBit1(probLen);

   458             probLen = prob + LenHigh;

   459             offset = kLenNumLowSymbols + kLenNumMidSymbols;

   460             numBits = kLenNumHighBits;

   461           }

   462         }

   463         RangeDecoderBitTreeDecode(probLen, numBits, len);

   464         len += offset;

   465       }

   466 

   467       if (state < 4)

   468       {

   469         int posSlot;

   470         state += kNumLitStates;

   471         prob = p + PosSlot +

   472             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << 

   473             kNumPosSlotBits);

   474         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);

   475         if (posSlot >= kStartPosModelIndex)

   476         {

   477           int numDirectBits = ((posSlot >> 1) - 1);

   478           rep0 = (2 | ((UInt32)posSlot & 1));

   479           if (posSlot < kEndPosModelIndex)

   480           {

   481             rep0 <<= numDirectBits;

   482             prob = p + SpecPos + rep0 - posSlot - 1;

   483           }

   484           else

   485           {

   486             numDirectBits -= kNumAlignBits;

   487             do

   488             {

   489               RC_NORMALIZE

   490               Range >>= 1;

   491               rep0 <<= 1;

   492               if (Code >= Range)

   493               {

   494                 Code -= Range;

   495                 rep0 |= 1;

   496               }

   497             }

   498             while (--numDirectBits != 0);

   499             prob = p + Align;

   500             rep0 <<= kNumAlignBits;

   501             numDirectBits = kNumAlignBits;

   502           }

   503           {

   504             int i = 1;

   505             int mi = 1;

   506             do

   507             {

   508               CProb *prob3 = prob + mi;

   509               RC_GET_BIT2(prob3, mi, ; , rep0 |= i);

   510               i <<= 1;

   511             }

   512             while(--numDirectBits != 0);

   513           }

   514         }

   515         else

   516           rep0 = posSlot;

   517         if (++rep0 == (UInt32)(0))

   518         {

   519           /* it's for stream version */

   520           len = kLzmaStreamWasFinishedId;

   521           break;

   522         }

   523       }

   524 

   525       len += kMatchMinLen;

   526       #ifdef _LZMA_OUT_READ

   527       if (rep0 > distanceLimit) 

   528       #else

   529       if (rep0 > nowPos)

   530       #endif

   531         return LZMA_RESULT_DATA_ERROR;

   532 

   533       #ifdef _LZMA_OUT_READ

   534       if (dictionarySize - distanceLimit > (UInt32)len)

   535         distanceLimit += len;

   536       else

   537         distanceLimit = dictionarySize;

   538       #endif

   539 

   540       do

   541       {

   542         #ifdef _LZMA_OUT_READ

   543         UInt32 pos = dictionaryPos - rep0;

   544         if (pos >= dictionarySize)

   545           pos += dictionarySize;

   546         previousByte = dictionary[pos];

   547         dictionary[dictionaryPos] = previousByte;

   548         if (++dictionaryPos == dictionarySize)

   549           dictionaryPos = 0;

   550         #else

   551         previousByte = outStream[nowPos - rep0];

   552         #endif

   553         len--;

   554         outStream[nowPos++] = previousByte;

   555       }

   556       while(len != 0 && nowPos < outSize);

   557     }

   558   }

   559   RC_NORMALIZE;

   560 

   561   #ifdef _LZMA_OUT_READ

   562   vs->Range = Range;

   563   vs->Code = Code;

   564   vs->DictionaryPos = dictionaryPos;

   565   vs->GlobalPos = globalPos + (UInt32)nowPos;

   566   vs->DistanceLimit = distanceLimit;

   567   vs->Reps[0] = rep0;

   568   vs->Reps[1] = rep1;

   569   vs->Reps[2] = rep2;

   570   vs->Reps[3] = rep3;

   571   vs->State = state;

   572   vs->RemainLen = len;

   573   vs->TempDictionary[0] = tempDictionary[0];

   574   #endif

   575 

   576   #ifdef _LZMA_IN_CB

   577   vs->Buffer = Buffer;

   578   vs->BufferLim = BufferLim;

   579   #else

   580   *inSizeProcessed = (SizeT)(Buffer - inStream);

   581   #endif

   582   *outSizeProcessed = nowPos;

   583   return LZMA_RESULT_OK;

   584 }