1 /*

     2   LzmaStateDecode.c

     3   LZMA Decoder (State 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 "LzmaStateDecode.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_INIT Code = 0; Range = 0xFFFFFFFF; \

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

    35 

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

    37 

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

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

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

    41 

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

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

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

    45   

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

    47 

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

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

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

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

    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 

    87 #define IsMatch 0

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

    89 #define IsRepG0 (IsRep + kNumStates)

    90 #define IsRepG1 (IsRepG0 + kNumStates)

    91 #define IsRepG2 (IsRepG1 + kNumStates)

    92 #define IsRep0Long (IsRepG2 + kNumStates)

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

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

    95 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)

    96 #define LenCoder (Align + kAlignTableSize)

    97 #define RepLenCoder (LenCoder + kNumLenProbs)

    98 #define Literal (RepLenCoder + kNumLenProbs)

    99 

   100 #if Literal != LZMA_BASE_SIZE

   101 StopCompilingDueBUG

   102 #endif

   103 

   104 /* kRequiredInBufferSize = number of required input bytes for worst case: 

   105    longest match with longest distance.

   106    kLzmaInBufferSize must be larger than kRequiredInBufferSize 

   107    23 bits = 2 (match select) + 10 (len) + 6 (distance) + 4(align) + 1 (RC_NORMALIZE)

   108 */

   109 

   110 #define kRequiredInBufferSize ((23 * (kNumBitModelTotalBits - kNumMoveBits + 1) + 26 + 9) / 8)

   111 

   112 #define kLzmaStreamWasFinishedId (-1)

   113 

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

   115 {

   116   unsigned char prop0;

   117   if (size < LZMA_PROPERTIES_SIZE)

   118     return LZMA_RESULT_DATA_ERROR;

   119   prop0 = propsData[0];

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

   121     return LZMA_RESULT_DATA_ERROR;

   122   {

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

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

   125     propsRes->lc = prop0;

   126     /*

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

   128     propsRes->lc = prop0 % 9;

   129     propsRes->pb = remainder / 5;

   130     propsRes->lp = remainder % 5;

   131     */

   132   }

   133 

   134   {

   135     int i;

   136     propsRes->DictionarySize = 0;

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

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

   139     if (propsRes->DictionarySize == 0)

   140       propsRes->DictionarySize = 1;

   141     return LZMA_RESULT_OK;

   142   }

   143 }

   144 

   145 int LzmaDecode(

   146     CLzmaDecoderState *vs,

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

   148     unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed,

   149     int finishDecoding)

   150 {

   151   UInt32 Range = vs->Range;

   152   UInt32 Code = vs->Code;

   153 

   154   unsigned char *Buffer = vs->Buffer;

   155   int BufferSize = vs->BufferSize; /* don't change it to unsigned int */

   156   CProb *p = vs->Probs;

   157 

   158   int state = vs->State;

   159   unsigned char previousByte;

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

   161   SizeT nowPos = 0;

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

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

   164   int lc = vs->Properties.lc;

   165   int len = vs->RemainLen;

   166   UInt32 globalPos = vs->GlobalPos;

   167   UInt32 distanceLimit = vs->DistanceLimit;

   168 

   169   unsigned char *dictionary = vs->Dictionary;

   170   UInt32 dictionarySize = vs->Properties.DictionarySize;

   171   UInt32 dictionaryPos = vs->DictionaryPos;

   172 

   173   unsigned char tempDictionary[4];

   174 

   175   (*inSizeProcessed) = 0;

   176   (*outSizeProcessed) = 0;

   177   if (len == kLzmaStreamWasFinishedId)

   178     return LZMA_RESULT_OK;

   179 

   180   if (dictionarySize == 0)

   181   {

   182     dictionary = tempDictionary;

   183     dictionarySize = 1;

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

   185   }

   186 

   187   if (len == kLzmaNeedInitId)

   188   {

   189     while (inSize > 0 && BufferSize < kLzmaInBufferSize)

   190     {

   191       Buffer[BufferSize++] = *inStream++;

   192       (*inSizeProcessed)++;

   193       inSize--;

   194     }

   195     if (BufferSize < 5)

   196     {

   197       vs->BufferSize = BufferSize;

   198       return finishDecoding ? LZMA_RESULT_DATA_ERROR : LZMA_RESULT_OK;

   199     }

   200     {

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

   202       UInt32 i;

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

   204         p[i] = kBitModelTotal >> 1; 

   205       rep0 = rep1 = rep2 = rep3 = 1;

   206       state = 0;

   207       globalPos = 0;

   208       distanceLimit = 0;

   209       dictionaryPos = 0;

   210       dictionary[dictionarySize - 1] = 0;

   211       RC_INIT;

   212     }

   213     len = 0;

   214   }

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

   216   {

   217     UInt32 pos = dictionaryPos - rep0;

   218     if (pos >= dictionarySize)

   219       pos += dictionarySize;

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

   221     if (++dictionaryPos == dictionarySize)

   222       dictionaryPos = 0;

   223     len--;

   224   }

   225   if (dictionaryPos == 0)

   226     previousByte = dictionary[dictionarySize - 1];

   227   else

   228     previousByte = dictionary[dictionaryPos - 1];

   229 

   230   for (;;)

   231   {

   232     int bufferPos = (int)(Buffer - vs->Buffer);

   233     if (BufferSize - bufferPos < kRequiredInBufferSize)

   234     {

   235       int i;

   236       BufferSize -= bufferPos;

   237       if (BufferSize < 0)

   238         return LZMA_RESULT_DATA_ERROR;

   239       for (i = 0; i < BufferSize; i++)

   240         vs->Buffer[i] = Buffer[i];

   241       Buffer = vs->Buffer;

   242       while (inSize > 0 && BufferSize < kLzmaInBufferSize)

   243       {

   244         Buffer[BufferSize++] = *inStream++;

   245         (*inSizeProcessed)++;

   246         inSize--;

   247       }

   248       if (BufferSize < kRequiredInBufferSize && !finishDecoding)

   249         break;

   250     }

   251     if (nowPos >= outSize)

   252       break;

   253     {

   254     CProb *prob;

   255     UInt32 bound;

   256     int posState = (int)((nowPos + globalPos) & posStateMask);

   257 

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

   259     IfBit0(prob)

   260     {

   261       int symbol = 1;

   262       UpdateBit0(prob)

   263       prob = p + Literal + (LZMA_LIT_SIZE * 

   264         ((((nowPos + globalPos)& literalPosMask) << lc) + (previousByte >> (8 - lc))));

   265 

   266       if (state >= kNumLitStates)

   267       {

   268         int matchByte;

   269         UInt32 pos = dictionaryPos - rep0;

   270         if (pos >= dictionarySize)

   271           pos += dictionarySize;

   272         matchByte = dictionary[pos];

   273         do

   274         {

   275           int bit;

   276           CProb *probLit;

   277           matchByte <<= 1;

   278           bit = (matchByte & 0x100);

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

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

   281         }

   282         while (symbol < 0x100);

   283       }

   284       while (symbol < 0x100)

   285       {

   286         CProb *probLit = prob + symbol;

   287         RC_GET_BIT(probLit, symbol)

   288       }

   289       previousByte = (unsigned char)symbol;

   290 

   291       outStream[nowPos++] = previousByte;

   292       if (distanceLimit < dictionarySize)

   293         distanceLimit++;

   294 

   295       dictionary[dictionaryPos] = previousByte;

   296       if (++dictionaryPos == dictionarySize)

   297         dictionaryPos = 0;

   298       if (state < 4) state = 0;

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

   300       else state -= 6;

   301     }

   302     else             

   303     {

   304       UpdateBit1(prob);

   305       prob = p + IsRep + state;

   306       IfBit0(prob)

   307       {

   308         UpdateBit0(prob);

   309         rep3 = rep2;

   310         rep2 = rep1;

   311         rep1 = rep0;

   312         state = state < kNumLitStates ? 0 : 3;

   313         prob = p + LenCoder;

   314       }

   315       else

   316       {

   317         UpdateBit1(prob);

   318         prob = p + IsRepG0 + state;

   319         IfBit0(prob)

   320         {

   321           UpdateBit0(prob);

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

   323           IfBit0(prob)

   324           {

   325             UInt32 pos;

   326             UpdateBit0(prob);

   327             if (distanceLimit == 0)

   328               return LZMA_RESULT_DATA_ERROR;

   329             if (distanceLimit < dictionarySize)

   330               distanceLimit++;

   331             state = state < kNumLitStates ? 9 : 11;

   332             pos = dictionaryPos - rep0;

   333             if (pos >= dictionarySize)

   334               pos += dictionarySize;

   335             previousByte = dictionary[pos];

   336             dictionary[dictionaryPos] = previousByte;

   337             if (++dictionaryPos == dictionarySize)

   338               dictionaryPos = 0;

   339             outStream[nowPos++] = previousByte;

   340             continue;

   341           }

   342           else

   343           {

   344             UpdateBit1(prob);

   345           }

   346         }

   347         else

   348         {

   349           UInt32 distance;

   350           UpdateBit1(prob);

   351           prob = p + IsRepG1 + state;

   352           IfBit0(prob)

   353           {

   354             UpdateBit0(prob);

   355             distance = rep1;

   356           }

   357           else 

   358           {

   359             UpdateBit1(prob);

   360             prob = p + IsRepG2 + state;

   361             IfBit0(prob)

   362             {

   363               UpdateBit0(prob);

   364               distance = rep2;

   365             }

   366             else

   367             {

   368               UpdateBit1(prob);

   369               distance = rep3;

   370               rep3 = rep2;

   371             }

   372             rep2 = rep1;

   373           }

   374           rep1 = rep0;

   375           rep0 = distance;

   376         }

   377         state = state < kNumLitStates ? 8 : 11;

   378         prob = p + RepLenCoder;

   379       }

   380       {

   381         int numBits, offset;

   382         CProb *probLen = prob + LenChoice;

   383         IfBit0(probLen)

   384         {

   385           UpdateBit0(probLen);

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

   387           offset = 0;

   388           numBits = kLenNumLowBits;

   389         }

   390         else

   391         {

   392           UpdateBit1(probLen);

   393           probLen = prob + LenChoice2;

   394           IfBit0(probLen)

   395           {

   396             UpdateBit0(probLen);

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

   398             offset = kLenNumLowSymbols;

   399             numBits = kLenNumMidBits;

   400           }

   401           else

   402           {

   403             UpdateBit1(probLen);

   404             probLen = prob + LenHigh;

   405             offset = kLenNumLowSymbols + kLenNumMidSymbols;

   406             numBits = kLenNumHighBits;

   407           }

   408         }

   409         RangeDecoderBitTreeDecode(probLen, numBits, len);

   410         len += offset;

   411       }

   412 

   413       if (state < 4)

   414       {

   415         int posSlot;

   416         state += kNumLitStates;

   417         prob = p + PosSlot +

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

   419             kNumPosSlotBits);

   420         RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);

   421         if (posSlot >= kStartPosModelIndex)

   422         {

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

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

   425           if (posSlot < kEndPosModelIndex)

   426           {

   427             rep0 <<= numDirectBits;

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

   429           }

   430           else

   431           {

   432             numDirectBits -= kNumAlignBits;

   433             do

   434             {

   435               RC_NORMALIZE

   436               Range >>= 1;

   437               rep0 <<= 1;

   438               if (Code >= Range)

   439               {

   440                 Code -= Range;

   441                 rep0 |= 1;

   442               }

   443             }

   444             while (--numDirectBits != 0);

   445             prob = p + Align;

   446             rep0 <<= kNumAlignBits;

   447             numDirectBits = kNumAlignBits;

   448           }

   449           {

   450             int i = 1;

   451             int mi = 1;

   452             do

   453             {

   454               CProb *prob3 = prob + mi;

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

   456               i <<= 1;

   457             }

   458             while(--numDirectBits != 0);

   459           }

   460         }

   461         else

   462           rep0 = posSlot;

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

   464         {

   465           /* it's for stream version */

   466           len = kLzmaStreamWasFinishedId;

   467           break;

   468         }

   469       }

   470 

   471       len += kMatchMinLen;

   472       if (rep0 > distanceLimit) 

   473         return LZMA_RESULT_DATA_ERROR;

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

   475         distanceLimit += len;

   476       else

   477         distanceLimit = dictionarySize;

   478 

   479       do

   480       {

   481         UInt32 pos = dictionaryPos - rep0;

   482         if (pos >= dictionarySize)

   483           pos += dictionarySize;

   484         previousByte = dictionary[pos];

   485         dictionary[dictionaryPos] = previousByte;

   486         if (++dictionaryPos == dictionarySize)

   487           dictionaryPos = 0;

   488         len--;

   489         outStream[nowPos++] = previousByte;

   490       }

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

   492     }

   493     }

   494   }

   495   RC_NORMALIZE;

   496 

   497   BufferSize -= (int)(Buffer - vs->Buffer);

   498   if (BufferSize < 0)

   499     return LZMA_RESULT_DATA_ERROR;

   500   {

   501     int i;

   502     for (i = 0; i < BufferSize; i++)

   503       vs->Buffer[i] = Buffer[i];

   504   }

   505   vs->BufferSize = BufferSize;

   506   vs->Range = Range;

   507   vs->Code = Code;

   508   vs->DictionaryPos = dictionaryPos;

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

   510   vs->DistanceLimit = distanceLimit;

   511   vs->Reps[0] = rep0;

   512   vs->Reps[1] = rep1;

   513   vs->Reps[2] = rep2;

   514   vs->Reps[3] = rep3;

   515   vs->State = state;

   516   vs->RemainLen = len;

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

   518 

   519   (*outSizeProcessed) = nowPos;

   520   return LZMA_RESULT_OK;

   521 }