1/*
2  LzmaDecode.c
3  LZMA Decoder
4
5  LZMA SDK 4.05 Copyright (c) 1999-2004 Igor Pavlov (2004-08-25)
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
35typedef struct _CRangeDecoder
36{
37  Byte *Buffer;
38  Byte *BufferLim;
39  UInt32 Range;
40  UInt32 Code;
41  #ifdef _LZMA_IN_CB
42  ILzmaInCallback *InCallback;
43  int Result;
44  #endif
45  int ExtraBytes;
46} CRangeDecoder;
47
48Byte RangeDecoderReadByte(CRangeDecoder *rd)
49{
50  if (rd->Buffer == rd->BufferLim)
51  {
52    #ifdef _LZMA_IN_CB
53    UInt32 size;
54    rd->Result = rd->InCallback->Read(rd->InCallback, &rd->Buffer, &size);
55    rd->BufferLim = rd->Buffer + size;
56    if (size == 0)
57    #endif
58    {
59      rd->ExtraBytes = 1;
60      return 0xFF;
61    }
62  }
63  return (*rd->Buffer++);
64}
65
66/* #define ReadByte (*rd->Buffer++) */
67#define ReadByte (RangeDecoderReadByte(rd))
68
69void RangeDecoderInit(CRangeDecoder *rd,
70  #ifdef _LZMA_IN_CB
71    ILzmaInCallback *inCallback
72  #else
73    Byte *stream, UInt32 bufferSize
74  #endif
75    )
76{
77  int i;
78  #ifdef _LZMA_IN_CB
79  rd->InCallback = inCallback;
80  rd->Buffer = rd->BufferLim = 0;
81  #else
82  rd->Buffer = stream;
83  rd->BufferLim = stream + bufferSize;
84  #endif
85  rd->ExtraBytes = 0;
86  rd->Code = 0;
87  rd->Range = (0xFFFFFFFF);
88  for(i = 0; i < 5; i++)
89    rd->Code = (rd->Code << 8) | ReadByte;
90}
91
92#define RC_INIT_VAR UInt32 range = rd->Range; UInt32 code = rd->Code;
93#define RC_FLUSH_VAR rd->Range = range; rd->Code = code;
94#define RC_NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | ReadByte; }
95
96UInt32 RangeDecoderDecodeDirectBits(CRangeDecoder *rd, int numTotalBits)
97{
98  RC_INIT_VAR
99  UInt32 result = 0;
100  int i;
101  for (i = numTotalBits; i > 0; i--)
102  {
103    /* UInt32 t; */
104    range >>= 1;
105
106    result <<= 1;
107    if (code >= range)
108    {
109      code -= range;
110      result |= 1;
111    }
112    /*
113    t = (code - range) >> 31;
114    t &= 1;
115    code -= range & (t - 1);
116    result = (result + result) | (1 - t);
117    */
118    RC_NORMALIZE
119  }
120  RC_FLUSH_VAR
121  return result;
122}
123
124int RangeDecoderBitDecode(CProb *prob, CRangeDecoder *rd)
125{
126  UInt32 bound = (rd->Range >> kNumBitModelTotalBits) * *prob;
127  if (rd->Code < bound)
128  {
129    rd->Range = bound;
130    *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
131    if (rd->Range < kTopValue)
132    {
133      rd->Code = (rd->Code << 8) | ReadByte;
134      rd->Range <<= 8;
135    }
136    return 0;
137  }
138  else
139  {
140    rd->Range -= bound;
141    rd->Code -= bound;
142    *prob -= (*prob) >> kNumMoveBits;
143    if (rd->Range < kTopValue)
144    {
145      rd->Code = (rd->Code << 8) | ReadByte;
146      rd->Range <<= 8;
147    }
148    return 1;
149  }
150}
151
152#define RC_GET_BIT2(prob, mi, A0, A1) \
153  UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \
154  if (code < bound) \
155    { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \
156  else \
157    { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \
158  RC_NORMALIZE
159
160#define RC_GET_BIT(prob, mi) RC_GET_BIT2(prob, mi, ; , ;)
161
162int RangeDecoderBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
163{
164  int mi = 1;
165  int i;
166  #ifdef _LZMA_LOC_OPT
167  RC_INIT_VAR
168  #endif
169  for(i = numLevels; i > 0; i--)
170  {
171    #ifdef _LZMA_LOC_OPT
172    CProb *prob = probs + mi;
173    RC_GET_BIT(prob, mi)
174    #else
175    mi = (mi + mi) + RangeDecoderBitDecode(probs + mi, rd);
176    #endif
177  }
178  #ifdef _LZMA_LOC_OPT
179  RC_FLUSH_VAR
180  #endif
181  return mi - (1 << numLevels);
182}
183
184int RangeDecoderReverseBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd)
185{
186  int mi = 1;
187  int i;
188  int symbol = 0;
189  #ifdef _LZMA_LOC_OPT
190  RC_INIT_VAR
191  #endif
192  for(i = 0; i < numLevels; i++)
193  {
194    #ifdef _LZMA_LOC_OPT
195    CProb *prob = probs + mi;
196    RC_GET_BIT2(prob, mi, ; , symbol |= (1 << i))
197    #else
198    int bit = RangeDecoderBitDecode(probs + mi, rd);
199    mi = mi + mi + bit;
200    symbol |= (bit << i);
201    #endif
202  }
203  #ifdef _LZMA_LOC_OPT
204  RC_FLUSH_VAR
205  #endif
206  return symbol;
207}
208
209Byte LzmaLiteralDecode(CProb *probs, CRangeDecoder *rd)
210{
211  int symbol = 1;
212  #ifdef _LZMA_LOC_OPT
213  RC_INIT_VAR
214  #endif
215  do
216  {
217    #ifdef _LZMA_LOC_OPT
218    CProb *prob = probs + symbol;
219    RC_GET_BIT(prob, symbol)
220    #else
221    symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
222    #endif
223  }
224  while (symbol < 0x100);
225  #ifdef _LZMA_LOC_OPT
226  RC_FLUSH_VAR
227  #endif
228  return symbol;
229}
230
231Byte LzmaLiteralDecodeMatch(CProb *probs, CRangeDecoder *rd, Byte matchByte)
232{
233  int symbol = 1;
234  #ifdef _LZMA_LOC_OPT
235  RC_INIT_VAR
236  #endif
237  do
238  {
239    int bit;
240    int matchBit = (matchByte >> 7) & 1;
241    matchByte <<= 1;
242    #ifdef _LZMA_LOC_OPT
243    {
244      CProb *prob = probs + ((1 + matchBit) << 8) + symbol;
245      RC_GET_BIT2(prob, symbol, bit = 0, bit = 1)
246    }
247    #else
248    bit = RangeDecoderBitDecode(probs + ((1 + matchBit) << 8) + symbol, rd);
249    symbol = (symbol << 1) | bit;
250    #endif
251    if (matchBit != bit)
252    {
253      while (symbol < 0x100)
254      {
255        #ifdef _LZMA_LOC_OPT
256        CProb *prob = probs + symbol;
257        RC_GET_BIT(prob, symbol)
258        #else
259        symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd);
260        #endif
261      }
262      break;
263    }
264  }
265  while (symbol < 0x100);
266  #ifdef _LZMA_LOC_OPT
267  RC_FLUSH_VAR
268  #endif
269  return symbol;
270}
271
272#define kNumPosBitsMax 4
273#define kNumPosStatesMax (1 << kNumPosBitsMax)
274
275#define kLenNumLowBits 3
276#define kLenNumLowSymbols (1 << kLenNumLowBits)
277#define kLenNumMidBits 3
278#define kLenNumMidSymbols (1 << kLenNumMidBits)
279#define kLenNumHighBits 8
280#define kLenNumHighSymbols (1 << kLenNumHighBits)
281
282#define LenChoice 0
283#define LenChoice2 (LenChoice + 1)
284#define LenLow (LenChoice2 + 1)
285#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
286#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
287#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
288
289int LzmaLenDecode(CProb *p, CRangeDecoder *rd, int posState)
290{
291  if(RangeDecoderBitDecode(p + LenChoice, rd) == 0)
292    return RangeDecoderBitTreeDecode(p + LenLow +
293        (posState << kLenNumLowBits), kLenNumLowBits, rd);
294  if(RangeDecoderBitDecode(p + LenChoice2, rd) == 0)
295    return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p + LenMid +
296        (posState << kLenNumMidBits), kLenNumMidBits, rd);
297  return kLenNumLowSymbols + kLenNumMidSymbols +
298      RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd);
299}
300
301#define kNumStates 12
302
303#define kStartPosModelIndex 4
304#define kEndPosModelIndex 14
305#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
306
307#define kNumPosSlotBits 6
308#define kNumLenToPosStates 4
309
310#define kNumAlignBits 4
311#define kAlignTableSize (1 << kNumAlignBits)
312
313#define kMatchMinLen 2
314
315#define IsMatch 0
316#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
317#define IsRepG0 (IsRep + kNumStates)
318#define IsRepG1 (IsRepG0 + kNumStates)
319#define IsRepG2 (IsRepG1 + kNumStates)
320#define IsRep0Long (IsRepG2 + kNumStates)
321#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
322#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
323#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
324#define LenCoder (Align + kAlignTableSize)
325#define RepLenCoder (LenCoder + kNumLenProbs)
326#define Literal (RepLenCoder + kNumLenProbs)
327
328#if Literal != LZMA_BASE_SIZE
329StopCompilingDueBUG
330#endif
331
332#ifdef _LZMA_OUT_READ
333
334typedef struct _LzmaVarState
335{
336  CRangeDecoder RangeDecoder;
337  Byte *Dictionary;
338  UInt32 DictionarySize;
339  UInt32 DictionaryPos;
340  UInt32 GlobalPos;
341  UInt32 Reps[4];
342  int lc;
343  int lp;
344  int pb;
345  int State;
346  int PreviousIsMatch;
347  int RemainLen;
348} LzmaVarState;
349
350int LzmaDecoderInit(
351    unsigned char *buffer, UInt32 bufferSize,
352    int lc, int lp, int pb,
353    unsigned char *dictionary, UInt32 dictionarySize,
354    #ifdef _LZMA_IN_CB
355    ILzmaInCallback *inCallback
356    #else
357    unsigned char *inStream, UInt32 inSize
358    #endif
359    )
360{
361  LzmaVarState *vs = (LzmaVarState *)buffer;
362  CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
363  UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
364  UInt32 i;
365  if (bufferSize < numProbs * sizeof(CProb) + sizeof(LzmaVarState))
366    return LZMA_RESULT_NOT_ENOUGH_MEM;
367  vs->Dictionary = dictionary;
368  vs->DictionarySize = dictionarySize;
369  vs->DictionaryPos = 0;
370  vs->GlobalPos = 0;
371  vs->Reps[0] = vs->Reps[1] = vs->Reps[2] = vs->Reps[3] = 1;
372  vs->lc = lc;
373  vs->lp = lp;
374  vs->pb = pb;
375  vs->State = 0;
376  vs->PreviousIsMatch = 0;
377  vs->RemainLen = 0;
378  dictionary[dictionarySize - 1] = 0;
379  for (i = 0; i < numProbs; i++)
380    p[i] = kBitModelTotal >> 1;
381  RangeDecoderInit(&vs->RangeDecoder,
382      #ifdef _LZMA_IN_CB
383      inCallback
384      #else
385      inStream, inSize
386      #endif
387  );
388  return LZMA_RESULT_OK;
389}
390
391int LzmaDecode(unsigned char *buffer,
392    unsigned char *outStream, UInt32 outSize,
393    UInt32 *outSizeProcessed)
394{
395  LzmaVarState *vs = (LzmaVarState *)buffer;
396  CProb *p = (CProb *)(buffer + sizeof(LzmaVarState));
397  CRangeDecoder rd = vs->RangeDecoder;
398  int state = vs->State;
399  int previousIsMatch = vs->PreviousIsMatch;
400  Byte previousByte;
401  UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
402  UInt32 nowPos = 0;
403  UInt32 posStateMask = (1 << (vs->pb)) - 1;
404  UInt32 literalPosMask = (1 << (vs->lp)) - 1;
405  int lc = vs->lc;
406  int len = vs->RemainLen;
407  UInt32 globalPos = vs->GlobalPos;
408
409  Byte *dictionary = vs->Dictionary;
410  UInt32 dictionarySize = vs->DictionarySize;
411  UInt32 dictionaryPos = vs->DictionaryPos;
412
413  if (len == -1)
414  {
415    *outSizeProcessed = 0;
416    return LZMA_RESULT_OK;
417  }
418
419  while(len > 0 && nowPos < outSize)
420  {
421    UInt32 pos = dictionaryPos - rep0;
422    if (pos >= dictionarySize)
423      pos += dictionarySize;
424    outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
425    if (++dictionaryPos == dictionarySize)
426      dictionaryPos = 0;
427    len--;
428  }
429  if (dictionaryPos == 0)
430    previousByte = dictionary[dictionarySize - 1];
431  else
432    previousByte = dictionary[dictionaryPos - 1];
433#else
434
435int LzmaDecode(
436    Byte *buffer, UInt32 bufferSize,
437    int lc, int lp, int pb,
438    #ifdef _LZMA_IN_CB
439    ILzmaInCallback *inCallback,
440    #else
441    unsigned char *inStream, UInt32 inSize,
442    #endif
443    unsigned char *outStream, UInt32 outSize,
444    UInt32 *outSizeProcessed)
445{
446  UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp));
447  CProb *p = (CProb *)buffer;
448  CRangeDecoder rd;
449  UInt32 i;
450  int state = 0;
451  int previousIsMatch = 0;
452  Byte previousByte = 0;
453  UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
454  UInt32 nowPos = 0;
455  UInt32 posStateMask = (1 << pb) - 1;
456  UInt32 literalPosMask = (1 << lp) - 1;
457  int len = 0;
458  if (bufferSize < numProbs * sizeof(CProb))
459    return LZMA_RESULT_NOT_ENOUGH_MEM;
460  for (i = 0; i < numProbs; i++)
461    p[i] = kBitModelTotal >> 1;
462  RangeDecoderInit(&rd,
463      #ifdef _LZMA_IN_CB
464      inCallback
465      #else
466      inStream, inSize
467      #endif
468      );
469#endif
470
471  *outSizeProcessed = 0;
472  while(nowPos < outSize)
473  {
474    int posState = (int)(
475        (nowPos
476        #ifdef _LZMA_OUT_READ
477        + globalPos
478        #endif
479        )
480        & posStateMask);
481    #ifdef _LZMA_IN_CB
482    if (rd.Result != LZMA_RESULT_OK)
483      return rd.Result;
484    #endif
485    if (rd.ExtraBytes != 0)
486      return LZMA_RESULT_DATA_ERROR;
487    if (RangeDecoderBitDecode(p + IsMatch + (state << kNumPosBitsMax) + posState, &rd) == 0)
488    {
489      CProb *probs = p + Literal + (LZMA_LIT_SIZE *
490        (((
491        (nowPos
492        #ifdef _LZMA_OUT_READ
493        + globalPos
494        #endif
495        )
496        & literalPosMask) << lc) + (previousByte >> (8 - lc))));
497
498      if (state < 4) state = 0;
499      else if (state < 10) state -= 3;
500      else state -= 6;
501      if (previousIsMatch)
502      {
503        Byte matchByte;
504        #ifdef _LZMA_OUT_READ
505        UInt32 pos = dictionaryPos - rep0;
506        if (pos >= dictionarySize)
507          pos += dictionarySize;
508        matchByte = dictionary[pos];
509        #else
510        matchByte = outStream[nowPos - rep0];
511        #endif
512        previousByte = LzmaLiteralDecodeMatch(probs, &rd, matchByte);
513        previousIsMatch = 0;
514      }
515      else
516        previousByte = LzmaLiteralDecode(probs, &rd);
517      outStream[nowPos++] = previousByte;
518      #ifdef _LZMA_OUT_READ
519      dictionary[dictionaryPos] = previousByte;
520      if (++dictionaryPos == dictionarySize)
521        dictionaryPos = 0;
522      #endif
523    }
524    else
525    {
526      previousIsMatch = 1;
527      if (RangeDecoderBitDecode(p + IsRep + state, &rd) == 1)
528      {
529        if (RangeDecoderBitDecode(p + IsRepG0 + state, &rd) == 0)
530        {
531          if (RangeDecoderBitDecode(p + IsRep0Long + (state << kNumPosBitsMax) + posState, &rd) == 0)
532          {
533            #ifdef _LZMA_OUT_READ
534            UInt32 pos;
535            #endif
536            if (
537               (nowPos
538                #ifdef _LZMA_OUT_READ
539                + globalPos
540                #endif
541               )
542               == 0)
543              return LZMA_RESULT_DATA_ERROR;
544            state = state < 7 ? 9 : 11;
545            #ifdef _LZMA_OUT_READ
546            pos = dictionaryPos - rep0;
547            if (pos >= dictionarySize)
548              pos += dictionarySize;
549            previousByte = dictionary[pos];
550            dictionary[dictionaryPos] = previousByte;
551            if (++dictionaryPos == dictionarySize)
552              dictionaryPos = 0;
553            #else
554            previousByte = outStream[nowPos - rep0];
555            #endif
556            outStream[nowPos++] = previousByte;
557            continue;
558          }
559        }
560        else
561        {
562          UInt32 distance;
563          if(RangeDecoderBitDecode(p + IsRepG1 + state, &rd) == 0)
564            distance = rep1;
565          else
566          {
567            if(RangeDecoderBitDecode(p + IsRepG2 + state, &rd) == 0)
568              distance = rep2;
569            else
570            {
571              distance = rep3;
572              rep3 = rep2;
573            }
574            rep2 = rep1;
575          }
576          rep1 = rep0;
577          rep0 = distance;
578        }
579        len = LzmaLenDecode(p + RepLenCoder, &rd, posState);
580        state = state < 7 ? 8 : 11;
581      }
582      else
583      {
584        int posSlot;
585        rep3 = rep2;
586        rep2 = rep1;
587        rep1 = rep0;
588        state = state < 7 ? 7 : 10;
589        len = LzmaLenDecode(p + LenCoder, &rd, posState);
590        posSlot = RangeDecoderBitTreeDecode(p + PosSlot +
591            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
592            kNumPosSlotBits), kNumPosSlotBits, &rd);
593        if (posSlot >= kStartPosModelIndex)
594        {
595          int numDirectBits = ((posSlot >> 1) - 1);
596          rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits);
597          if (posSlot < kEndPosModelIndex)
598          {
599            rep0 += RangeDecoderReverseBitTreeDecode(
600                p + SpecPos + rep0 - posSlot - 1, numDirectBits, &rd);
601          }
602          else
603          {
604            rep0 += RangeDecoderDecodeDirectBits(&rd,
605                numDirectBits - kNumAlignBits) << kNumAlignBits;
606            rep0 += RangeDecoderReverseBitTreeDecode(p + Align, kNumAlignBits, &rd);
607          }
608        }
609        else
610          rep0 = posSlot;
611        rep0++;
612      }
613      if (rep0 == (UInt32)(0))
614      {
615        /* it's for stream version */
616        len = -1;
617        break;
618      }
619      if (rep0 > nowPos
620        #ifdef _LZMA_OUT_READ
621        + globalPos
622        #endif
623        )
624      {
625        return LZMA_RESULT_DATA_ERROR;
626      }
627      len += kMatchMinLen;
628      do
629      {
630        #ifdef _LZMA_OUT_READ
631        UInt32 pos = dictionaryPos - rep0;
632        if (pos >= dictionarySize)
633          pos += dictionarySize;
634        previousByte = dictionary[pos];
635        dictionary[dictionaryPos] = previousByte;
636        if (++dictionaryPos == dictionarySize)
637          dictionaryPos = 0;
638        #else
639        previousByte = outStream[nowPos - rep0];
640        #endif
641        outStream[nowPos++] = previousByte;
642        len--;
643      }
644      while(len > 0 && nowPos < outSize);
645    }
646  }
647
648  #ifdef _LZMA_OUT_READ
649  vs->RangeDecoder = rd;
650  vs->DictionaryPos = dictionaryPos;
651  vs->GlobalPos = globalPos + nowPos;
652  vs->Reps[0] = rep0;
653  vs->Reps[1] = rep1;
654  vs->Reps[2] = rep2;
655  vs->Reps[3] = rep3;
656  vs->State = state;
657  vs->PreviousIsMatch = previousIsMatch;
658  vs->RemainLen = len;
659  #endif
660
661  *outSizeProcessed = nowPos;
662  return LZMA_RESULT_OK;
663}
664