1/*
2  LzmaDecode.c
3  LZMA Decoder (optimized for Speed version)
4
5  LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10)
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#ifndef Byte
25#define Byte unsigned char
26#endif
27
28#define kNumTopBits 24
29#define kTopValue ((UInt32)1 << kNumTopBits)
30
31#define kNumBitModelTotalBits 11
32#define kBitModelTotal (1 << kNumBitModelTotalBits)
33#define kNumMoveBits 5
34
35#define RC_READ_BYTE (*Buffer++)
36
37#define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
38  { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
39
40#ifdef _LZMA_IN_CB
41
42#define RC_TEST { if (Buffer == BufferLim) \
43  { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
44  BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
45
46#define RC_INIT Buffer = BufferLim = 0; RC_INIT2
47
48#else
49
50#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
51
52#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
53
54#endif
55
56#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
57
58#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
59#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
60#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
61
62#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
63  { UpdateBit0(p); mi <<= 1; A0; } else \
64  { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
65
66#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
67
68#define RangeDecoderBitTreeDecode(probs, numLevels, res) \
69  { int i = numLevels; res = 1; \
70  do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
71  res -= (1 << numLevels); }
72
73
74#define kNumPosBitsMax 4
75#define kNumPosStatesMax (1 << kNumPosBitsMax)
76
77#define kLenNumLowBits 3
78#define kLenNumLowSymbols (1 << kLenNumLowBits)
79#define kLenNumMidBits 3
80#define kLenNumMidSymbols (1 << kLenNumMidBits)
81#define kLenNumHighBits 8
82#define kLenNumHighSymbols (1 << kLenNumHighBits)
83
84#define LenChoice 0
85#define LenChoice2 (LenChoice + 1)
86#define LenLow (LenChoice2 + 1)
87#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
88#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
89#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
90
91
92#define kNumStates 12
93#define kNumLitStates 7
94
95#define kStartPosModelIndex 4
96#define kEndPosModelIndex 14
97#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
98
99#define kNumPosSlotBits 6
100#define kNumLenToPosStates 4
101
102#define kNumAlignBits 4
103#define kAlignTableSize (1 << kNumAlignBits)
104
105#define kMatchMinLen 2
106
107#define IsMatch 0
108#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
109#define IsRepG0 (IsRep + kNumStates)
110#define IsRepG1 (IsRepG0 + kNumStates)
111#define IsRepG2 (IsRepG1 + kNumStates)
112#define IsRep0Long (IsRepG2 + kNumStates)
113#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
114#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
115#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
116#define LenCoder (Align + kAlignTableSize)
117#define RepLenCoder (LenCoder + kNumLenProbs)
118#define Literal (RepLenCoder + kNumLenProbs)
119
120#if Literal != LZMA_BASE_SIZE
121StopCompilingDueBUG
122#endif
123
124#if 0
125int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
126{
127  unsigned char prop0;
128  if (size < LZMA_PROPERTIES_SIZE)
129    return LZMA_RESULT_DATA_ERROR;
130  prop0 = propsData[0];
131  if (prop0 >= (9 * 5 * 5))
132    return LZMA_RESULT_DATA_ERROR;
133  {
134    for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
135    for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
136    propsRes->lc = prop0;
137    /*
138    unsigned char remainder = (unsigned char)(prop0 / 9);
139    propsRes->lc = prop0 % 9;
140    propsRes->pb = remainder / 5;
141    propsRes->lp = remainder % 5;
142    */
143  }
144
145  #ifdef _LZMA_OUT_READ
146  {
147    int i;
148    propsRes->DictionarySize = 0;
149    for (i = 0; i < 4; i++)
150      propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
151    if (propsRes->DictionarySize == 0)
152      propsRes->DictionarySize = 1;
153  }
154  #endif
155  return LZMA_RESULT_OK;
156}
157#endif
158
159#define kLzmaStreamWasFinishedId (-1)
160
161int LzmaDecode(CLzmaDecoderState *vs,
162    #ifdef _LZMA_IN_CB
163    ILzmaInCallback *InCallback,
164    #else
165    const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
166    #endif
167    unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
168{
169  CProb *p = vs->Probs;
170  SizeT nowPos = 0;
171  Byte previousByte = 0;
172  UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
173  UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
174  int lc = vs->Properties.lc;
175
176  #ifdef _LZMA_OUT_READ
177
178  UInt32 Range = vs->Range;
179  UInt32 Code = vs->Code;
180  #ifdef _LZMA_IN_CB
181  const Byte *Buffer = vs->Buffer;
182  const Byte *BufferLim = vs->BufferLim;
183  #else
184  const Byte *Buffer = inStream;
185  const Byte *BufferLim = inStream + inSize;
186  #endif
187  int state = vs->State;
188  UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
189  int len = vs->RemainLen;
190  UInt32 globalPos = vs->GlobalPos;
191  UInt32 distanceLimit = vs->DistanceLimit;
192
193  Byte *dictionary = vs->Dictionary;
194  UInt32 dictionarySize = vs->Properties.DictionarySize;
195  UInt32 dictionaryPos = vs->DictionaryPos;
196
197  Byte tempDictionary[4];
198
199  #ifndef _LZMA_IN_CB
200  *inSizeProcessed = 0;
201  #endif
202  *outSizeProcessed = 0;
203  if (len == kLzmaStreamWasFinishedId)
204    return LZMA_RESULT_OK;
205
206  if (dictionarySize == 0)
207  {
208    dictionary = tempDictionary;
209    dictionarySize = 1;
210    tempDictionary[0] = vs->TempDictionary[0];
211  }
212
213  if (len == kLzmaNeedInitId)
214  {
215    {
216      UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
217      UInt32 i;
218      for (i = 0; i < numProbs; i++)
219        p[i] = kBitModelTotal >> 1;
220      rep0 = rep1 = rep2 = rep3 = 1;
221      state = 0;
222      globalPos = 0;
223      distanceLimit = 0;
224      dictionaryPos = 0;
225      dictionary[dictionarySize - 1] = 0;
226      #ifdef _LZMA_IN_CB
227      RC_INIT;
228      #else
229      RC_INIT(inStream, inSize);
230      #endif
231    }
232    len = 0;
233  }
234  while(len != 0 && nowPos < outSize)
235  {
236    UInt32 pos = dictionaryPos - rep0;
237    if (pos >= dictionarySize)
238      pos += dictionarySize;
239    outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
240    if (++dictionaryPos == dictionarySize)
241      dictionaryPos = 0;
242    len--;
243  }
244  if (dictionaryPos == 0)
245    previousByte = dictionary[dictionarySize - 1];
246  else
247    previousByte = dictionary[dictionaryPos - 1];
248
249  #else /* if !_LZMA_OUT_READ */
250
251  int state = 0;
252  UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
253  int len = 0;
254  const Byte *Buffer;
255  const Byte *BufferLim;
256  UInt32 Range;
257  UInt32 Code;
258
259  #ifndef _LZMA_IN_CB
260  *inSizeProcessed = 0;
261  #endif
262  *outSizeProcessed = 0;
263
264  {
265    UInt32 i;
266    UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
267    for (i = 0; i < numProbs; i++)
268      p[i] = kBitModelTotal >> 1;
269  }
270
271  #ifdef _LZMA_IN_CB
272  RC_INIT;
273  #else
274  RC_INIT(inStream, inSize);
275  #endif
276
277  #endif /* _LZMA_OUT_READ */
278
279  while(nowPos < outSize)
280  {
281    CProb *prob;
282    UInt32 bound;
283    int posState = (int)(
284        (nowPos
285        #ifdef _LZMA_OUT_READ
286        + globalPos
287        #endif
288        )
289        & posStateMask);
290
291    prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
292    IfBit0(prob)
293    {
294      int symbol = 1;
295      UpdateBit0(prob)
296      prob = p + Literal + (LZMA_LIT_SIZE *
297        (((
298        (nowPos
299        #ifdef _LZMA_OUT_READ
300        + globalPos
301        #endif
302        )
303        & literalPosMask) << lc) + (previousByte >> (8 - lc))));
304
305      if (state >= kNumLitStates)
306      {
307        int matchByte;
308        #ifdef _LZMA_OUT_READ
309        UInt32 pos = dictionaryPos - rep0;
310        if (pos >= dictionarySize)
311          pos += dictionarySize;
312        matchByte = dictionary[pos];
313        #else
314        matchByte = outStream[nowPos - rep0];
315        #endif
316        do
317        {
318          int bit;
319          CProb *probLit;
320          matchByte <<= 1;
321          bit = (matchByte & 0x100);
322          probLit = prob + 0x100 + bit + symbol;
323          RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
324        }
325        while (symbol < 0x100);
326      }
327      while (symbol < 0x100)
328      {
329        CProb *probLit = prob + symbol;
330        RC_GET_BIT(probLit, symbol)
331      }
332      previousByte = (Byte)symbol;
333
334      outStream[nowPos++] = previousByte;
335      #ifdef _LZMA_OUT_READ
336      if (distanceLimit < dictionarySize)
337        distanceLimit++;
338
339      dictionary[dictionaryPos] = previousByte;
340      if (++dictionaryPos == dictionarySize)
341        dictionaryPos = 0;
342      #endif
343      if (state < 4) state = 0;
344      else if (state < 10) state -= 3;
345      else state -= 6;
346    }
347    else
348    {
349      UpdateBit1(prob);
350      prob = p + IsRep + state;
351      IfBit0(prob)
352      {
353        UpdateBit0(prob);
354        rep3 = rep2;
355        rep2 = rep1;
356        rep1 = rep0;
357        state = state < kNumLitStates ? 0 : 3;
358        prob = p + LenCoder;
359      }
360      else
361      {
362        UpdateBit1(prob);
363        prob = p + IsRepG0 + state;
364        IfBit0(prob)
365        {
366          UpdateBit0(prob);
367          prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
368          IfBit0(prob)
369          {
370            #ifdef _LZMA_OUT_READ
371            UInt32 pos;
372            #endif
373            UpdateBit0(prob);
374
375            #ifdef _LZMA_OUT_READ
376            if (distanceLimit == 0)
377            #else
378            if (nowPos == 0)
379            #endif
380              return LZMA_RESULT_DATA_ERROR;
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        return LZMA_RESULT_DATA_ERROR;
538
539      #ifdef _LZMA_OUT_READ
540      if (dictionarySize - distanceLimit > (UInt32)len)
541        distanceLimit += len;
542      else
543        distanceLimit = dictionarySize;
544      #endif
545
546      do
547      {
548        #ifdef _LZMA_OUT_READ
549        UInt32 pos = dictionaryPos - rep0;
550        if (pos >= dictionarySize)
551          pos += dictionarySize;
552        previousByte = dictionary[pos];
553        dictionary[dictionaryPos] = previousByte;
554        if (++dictionaryPos == dictionarySize)
555          dictionaryPos = 0;
556        #else
557        previousByte = outStream[nowPos - rep0];
558        #endif
559        len--;
560        outStream[nowPos++] = previousByte;
561      }
562      while(len != 0 && nowPos < outSize);
563    }
564  }
565  RC_NORMALIZE;
566
567  #ifdef _LZMA_OUT_READ
568  vs->Range = Range;
569  vs->Code = Code;
570  vs->DictionaryPos = dictionaryPos;
571  vs->GlobalPos = globalPos + (UInt32)nowPos;
572  vs->DistanceLimit = distanceLimit;
573  vs->Reps[0] = rep0;
574  vs->Reps[1] = rep1;
575  vs->Reps[2] = rep2;
576  vs->Reps[3] = rep3;
577  vs->State = state;
578  vs->RemainLen = len;
579  vs->TempDictionary[0] = tempDictionary[0];
580  #endif
581
582  #ifdef _LZMA_IN_CB
583  vs->Buffer = Buffer;
584  vs->BufferLim = BufferLim;
585  #else
586  *inSizeProcessed = (SizeT)(Buffer - inStream);
587  #endif
588  *outSizeProcessed = nowPos;
589  return LZMA_RESULT_OK;
590}
591