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
101StopCompilingDueBUG
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
114int 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
145int 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}
522