diff options
| author | Didier Raboud <odyx@debian.org> | 2018-03-31 20:38:02 +0200 |
|---|---|---|
| committer | Didier Raboud <odyx@debian.org> | 2018-03-31 20:38:02 +0200 |
| commit | ec6389c74b951dcbbcd8b6d3892470b06504737a (patch) | |
| tree | e03a7e9bf0d31c7c64055115af1b1374b5a0b5b9 /Source/7zip/LZMADecode.c | |
Import Upstream version 2.06
Diffstat (limited to 'Source/7zip/LZMADecode.c')
| -rw-r--r-- | Source/7zip/LZMADecode.c | 537 |
1 files changed, 537 insertions, 0 deletions
diff --git a/Source/7zip/LZMADecode.c b/Source/7zip/LZMADecode.c new file mode 100644 index 0000000..a7300e9 --- /dev/null +++ b/Source/7zip/LZMADecode.c @@ -0,0 +1,537 @@ +/*
+LzmaDecode.c
+LZMA Decoder
+LZMA SDK 4.01 Copyright (c) 1999-2004 Igor Pavlov (2004-02-15)
+
+Converted to a state machine by Amir Szekely
+*/
+
+#include <stdlib.h>
+#include "LZMADecode.h"
+
+#define LEAVE { goto saveStateAndReturn; }
+#define NEED_BYTE(c) case c: if (!avail_in) { mode = c; LEAVE; }
+#define NEED_BYTE_ if (!avail_in) LEAVE;
+#define NEXT_BYTE (avail_in--, *next_in++)
+#define NEED_OUT(c) case c: if (!avail_out) { mode = c; LEAVE; }
+#define PUT_BYTE_(b) { *next_out = b; next_out++; avail_out--; }
+#define PUT_BYTE(b) { totalOut++; PUT_BYTE_(b) }
+#define DECODE_BIT(c, x) prob = x; last = c; goto _LZMA_C_RDBD; case c:
+#define DECODE_LEN(c, x) probs = x; last2 = c; goto _LZMA_C_LEND; case c:
+#define DECODE_BIT_TREE(c, x, y) probs = x; numLevels = y; last3 = c; goto _LZMA_C_BTD; case c:
+
+enum {
+ /* 0 */ LZMA_C_INIT = 0,
+ /* 1 */ LZMA_C_GETDICT,
+ /* 2 */ LZMA_C_BLOCK,
+ /* 3 */ LZMA_C_RDI, /* RangeDecoderInit */
+ /* 4 */ LZMA_C_RDBD, /* RangeDecoderBitDecode */
+ /* 5 */ LZMA_C_RDBD_IN, /* RangeDecoderBitDecode */
+ /* 6 */ LZMA_C_TYPE,
+ /* 7 */ LZMA_C_ISREP,
+ /* 8 */ LZMA_C_ISREPG0,
+ /* 9 */ LZMA_C_ISREP0LONG,
+ /* 10 */ LZMA_C_ISREPG1,
+ /* 11 */ LZMA_C_ISREPG2,
+ /* 12 */ LZMA_C_NORM,
+ /* 13 */ LZMA_C_LITDM1, /* LzmaLiteralDecodeMatch */
+ /* 14 */ LZMA_C_LITDM2, /* LzmaLiteralDecodeMatch */
+ /* 15 */ LZMA_C_LITD, /* LzmaLiteralDecode */
+ /* 16 */ LZMA_C_RDRBTD, /* RangeDecoderReverseBitTreeDecode */
+ /* 17 */ LZMA_C_LEND, /* LzmaLenDecode */
+ /* 18 */ LZMA_C_LEND1, /* LzmaLenDecode */
+ /* 19 */ LZMA_C_LEND2, /* LzmaLenDecode */
+ /* 20 */ LZMA_C_LEND_RES, /* LzmaLenDecode */
+ /* 21 */ LZMA_C_LEND_C1,
+ /* 22 */ LZMA_C_LEND_C2,
+ /* 23 */ LZMA_C_BTD, /* RangeDecoderBitTreeDecode */
+ /* 24 */ LZMA_C_BTD_LOOP,
+ /* 25 */ LZMA_C_BTD_C1,
+ /* 26 */ LZMA_C_OUTPUT_1,
+ /* 27 */ LZMA_C_OUTPUT_2,
+ /* 28 */ LZMA_C_OUTPUT_3
+};
+
+#define kNumTopBits 24
+#define kTopValue ((UInt32)1 << kNumTopBits)
+
+#define kNumBitModelTotalBits 11
+#define kBitModelTotal (1 << kNumBitModelTotalBits)
+#define kNumMoveBits 5
+
+#define RC_NORMALIZE(c) if (range < kTopValue) { NEED_BYTE(c); range <<= 8; code = (code << 8) | NEXT_BYTE; }
+
+#define RC_GET_BIT2(c, prob, mi, A0, A1) { \
+ UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \
+ if (code < bound) \
+ { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \
+ else \
+ { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \
+ RC_NORMALIZE(c) \
+}
+
+#define RC_GET_BIT(c, prob, mi) RC_GET_BIT2(c, prob, mi, ; , ;)
+
+#define kNumPosBitsMax 4
+#define kNumPosStatesMax (1 << kNumPosBitsMax)
+
+#define kLenNumLowBits 3
+#define kLenNumLowSymbols (1 << kLenNumLowBits)
+#define kLenNumMidBits 3
+#define kLenNumMidSymbols (1 << kLenNumMidBits)
+#define kLenNumHighBits 8
+#define kLenNumHighSymbols (1 << kLenNumHighBits)
+
+#define LenChoice 0
+#define LenChoice2 (LenChoice + 1)
+#define LenLow (LenChoice2 + 1)
+#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
+#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
+#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
+
+#define kNumStates 12
+
+#define kStartPosModelIndex 4
+#define kEndPosModelIndex 14
+#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
+
+#define kNumPosSlotBits 6
+#define kNumLenToPosStates 4
+
+#define kNumAlignBits 4
+#define kAlignTableSize (1 << kNumAlignBits)
+
+#define kMatchMinLen 2
+
+#define IsMatch 0
+#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
+#define IsRepG0 (IsRep + kNumStates)
+#define IsRepG1 (IsRepG0 + kNumStates)
+#define IsRepG2 (IsRepG1 + kNumStates)
+#define IsRep0Long (IsRepG2 + kNumStates)
+#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
+#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
+#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
+#define LenCoder (Align + kAlignTableSize)
+#define RepLenCoder (LenCoder + kNumLenProbs)
+#define Literal (RepLenCoder + kNumLenProbs)
+
+#define LZMA_BASE_SIZE 1846
+#define LZMA_LIT_SIZE 768
+
+#if Literal != LZMA_BASE_SIZE
+StopCompilingDueBUG
+#endif
+
+void LZMACALL lzmaInit(lzma_stream *s)
+{
+ /* size of lzma_stream minus the size of the two allocated buffer pointers.
+ we don't want to lose to pointer or else we won't be able to free them. */
+ size_t i = sizeof(lzma_stream) - (sizeof(unsigned char *) * 2);
+ while (i--)
+ ((Byte *)s)[i] = 0;
+
+ s->rep0 = s->rep1 = s->rep2 = s->rep3 = 1;
+ s->range = (0xFFFFFFFF);
+}
+
+int LZMACALL lzmaDecode(lzma_stream *s)
+{
+ /* restore decoder state */
+ lzma_stream _s = *s;
+
+#define mode _s.mode
+#define last _s.last
+#define last2 _s.last2
+#define last3 _s.last3
+
+#define p ((CProb *) _s.dynamicData)
+#define dynamicDataSize _s.dynamicDataSize
+
+#define state _s.state
+#define isPreviousMatch _s.isPreviousMatch
+#define previousByte _s.previousByte
+#define rep0 _s.rep0
+#define rep1 _s.rep1
+#define rep2 _s.rep2
+#define rep3 _s.rep3
+#define lc _s.lc
+#define len _s.len
+#define totalOut _s.totalOut
+
+#define dictionary _s.dictionary
+#define dictionarySize _s.dictionarySize
+#define dictionaryPos _s.dictionaryPos
+
+#define posStateMask _s.posStateMask
+#define literalPosMask _s.literalPosMask
+
+#define avail_in _s.avail_in
+#define next_in _s.next_in
+#define avail_out _s.avail_out
+#define next_out _s.next_out
+
+#define range _s.range
+#define code _s.code
+
+#define probs _s.probs
+#define prob _s.prob
+
+#define symbol _s.temp2
+#define bit _s.temp3
+#define matchBit _s.temp1
+#define i _s.temp1
+#define result _s.temp2
+#define numLevels _s.temp3
+#define posSlot _s.temp2
+#define newDictionarySize ((UInt32) _s.temp3)
+
+#define matchByte _s.matchByte
+#define mi _s.mi
+#define posState _s.posState
+
+ if (len == -1)
+ return LZMA_STREAM_END;
+
+ for (;;) switch (mode)
+ {
+ case LZMA_C_INIT:
+ {
+ Byte firstByte;
+ UInt32 newDynamicDataSize;
+ UInt32 numProbs;
+ int lp;
+ int pb;
+
+ NEED_BYTE_;
+
+ firstByte = NEXT_BYTE;
+
+ if (firstByte > (9*5*5))
+ return LZMA_DATA_ERROR;
+
+ pb = firstByte / (9*5);
+ firstByte %= (9*5);
+ lp = firstByte / 9;
+ firstByte %= 9;
+ lc = firstByte;
+
+ posStateMask = (1 << (pb)) - 1;
+ literalPosMask = (1 << (lp)) - 1;
+
+ numProbs = Literal + (LZMA_LIT_SIZE << (lc + pb));
+ newDynamicDataSize = numProbs * sizeof(CProb);
+
+ if (newDynamicDataSize != dynamicDataSize)
+ {
+ if (p)
+ lzmafree(p);
+ p = lzmaalloc(newDynamicDataSize);
+ if (!p)
+ return LZMA_NOT_ENOUGH_MEM;
+ dynamicDataSize = newDynamicDataSize;
+ }
+
+ while (numProbs--)
+ p[numProbs] = kBitModelTotal >> 1;
+
+ for (i = 0, newDictionarySize = 0; i < 4; i++)
+ {
+ NEED_BYTE(LZMA_C_GETDICT);
+ newDictionarySize |= NEXT_BYTE << (i * 8);
+ }
+
+ if (newDictionarySize != dictionarySize)
+ {
+ dictionarySize = newDictionarySize;
+ if (dictionary)
+ lzmafree(dictionary);
+ dictionary = lzmaalloc(dictionarySize);
+ if (!dictionary)
+ return LZMA_NOT_ENOUGH_MEM;
+ }
+
+ dictionary[dictionarySize - 1] = 0;
+
+ i = 5;
+ while (i--)
+ {
+ NEED_BYTE(LZMA_C_RDI);
+ code = (code << 8) | NEXT_BYTE;
+ }
+ }
+ case LZMA_C_BLOCK:
+ posState = (int)(totalOut & posStateMask);
+ DECODE_BIT(LZMA_C_TYPE, p + IsMatch + (state << kNumPosBitsMax) + posState);
+ if (bit == 0)
+ {
+ probs = p + Literal + (LZMA_LIT_SIZE *
+ (((totalOut & literalPosMask) << lc) + (previousByte >> (8 - lc))));
+
+ if (state < 4) state = 0;
+ else if (state < 10) state -= 3;
+ else state -= 6;
+ if (isPreviousMatch)
+ {
+ UInt32 pos = dictionaryPos - rep0;
+ if (pos >= dictionarySize)
+ pos += dictionarySize;
+ matchByte = dictionary[pos];
+ {
+ symbol = 1;
+ do
+ {
+ matchBit = (matchByte >> 7) & 1;
+ matchByte <<= 1;
+ {
+ prob = probs + ((1 + matchBit) << 8) + symbol;
+ RC_GET_BIT2(LZMA_C_LITDM1, prob, symbol, bit = 0, bit = 1)
+ }
+ if (matchBit != bit)
+ {
+ while (symbol < 0x100)
+ {
+ prob = probs + symbol;
+ RC_GET_BIT(LZMA_C_LITDM2, prob, symbol)
+ }
+ break;
+ }
+ }
+ while (symbol < 0x100);
+ previousByte = symbol;
+ }
+ isPreviousMatch = 0;
+ }
+ else
+ {
+ symbol = 1;
+ do
+ {
+ prob = probs + symbol;
+ RC_GET_BIT(LZMA_C_LITD, prob, symbol)
+ }
+ while (symbol < 0x100);
+ previousByte = symbol;
+ }
+ NEED_OUT(LZMA_C_OUTPUT_1);
+ PUT_BYTE(previousByte);
+ dictionary[dictionaryPos] = previousByte;
+ dictionaryPos = (dictionaryPos + 1) % dictionarySize;
+ }
+ /* bit == 1 */
+ else
+ {
+ isPreviousMatch = 1;
+ DECODE_BIT(LZMA_C_ISREP, p + IsRep + state);
+ if (bit == 1)
+ {
+ DECODE_BIT(LZMA_C_ISREPG0, p + IsRepG0 + state);
+ if (bit == 0)
+ {
+ DECODE_BIT(LZMA_C_ISREP0LONG, p + IsRep0Long + (state << kNumPosBitsMax) + posState);
+ if (bit == 0)
+ {
+ UInt32 pos;
+ if (totalOut == 0)
+ return LZMA_DATA_ERROR;
+ state = state < 7 ? 9 : 11;
+ NEED_OUT(LZMA_C_OUTPUT_2);
+ pos = dictionaryPos - rep0;
+ if (pos >= dictionarySize)
+ pos += dictionarySize;
+ previousByte = dictionary[pos];
+ dictionary[dictionaryPos] = previousByte;
+ dictionaryPos = (dictionaryPos + 1) % dictionarySize;
+ PUT_BYTE(previousByte);
+ mode = LZMA_C_BLOCK;
+ break;
+ }
+ }
+ else
+ {
+ UInt32 distance;
+ DECODE_BIT(LZMA_C_ISREPG1, p + IsRepG1 + state);
+ if (bit == 0)
+ {
+ distance = rep1;
+ }
+ else
+ {
+ DECODE_BIT(LZMA_C_ISREPG2, p + IsRepG2 + state);
+ if (bit == 0)
+ distance = rep2;
+ else
+ {
+ distance = rep3;
+ rep3 = rep2;
+ }
+ rep2 = rep1;
+ }
+ rep1 = rep0;
+ rep0 = distance;
+ }
+ DECODE_LEN(LZMA_C_LEND_C1, p + RepLenCoder);
+ state = state < 7 ? 8 : 11;
+ }
+ else
+ {
+ rep3 = rep2;
+ rep2 = rep1;
+ rep1 = rep0;
+ state = state < 7 ? 7 : 10;
+ DECODE_LEN(LZMA_C_LEND_C2, p + LenCoder);
+ DECODE_BIT_TREE(
+ LZMA_C_BTD_C1,
+ p + PosSlot + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits),
+ kNumPosSlotBits
+ );
+ if (posSlot >= kStartPosModelIndex)
+ {
+ int numDirectBits = ((posSlot >> 1) - 1);
+ rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits);
+ if (posSlot < kEndPosModelIndex)
+ {
+ probs = p + SpecPos + rep0 - posSlot - 1;
+ numLevels = numDirectBits;
+ }
+ else
+ {
+ int numTotalBits = numDirectBits - kNumAlignBits;
+ result = 0;
+ for (i = numTotalBits; i > 0; i--)
+ {
+ /* UInt32 t; */
+ range >>= 1;
+
+ result <<= 1;
+ if (code >= range)
+ {
+ code -= range;
+ result |= 1;
+ }
+ /*
+ t = (code - range) >> 31;
+ t &= 1;
+ code -= range & (t - 1);
+ result = (result + result) | (1 - t);
+ */
+ RC_NORMALIZE(LZMA_C_NORM)
+ }
+ rep0 += result << kNumAlignBits;
+ probs = p + Align;
+ numLevels = kNumAlignBits;
+ }
+ mi = 1;
+ symbol = 0;
+ for(i = 0; i < numLevels; i++)
+ {
+ prob = probs + mi;
+ RC_GET_BIT2(LZMA_C_RDRBTD, prob, mi, ; , symbol |= (1 << i));
+ }
+ rep0 += symbol;
+ }
+ else
+ rep0 = posSlot;
+ rep0++;
+ }
+ if (rep0 == (UInt32)(0))
+ {
+ len = -1;
+ LEAVE;
+ }
+ if (rep0 > totalOut)
+ {
+ return LZMA_DATA_ERROR;
+ }
+ len += kMatchMinLen;
+ totalOut += len;
+ do
+ {
+ UInt32 pos;
+ NEED_OUT(LZMA_C_OUTPUT_3);
+ pos = dictionaryPos - rep0;
+ if (pos >= dictionarySize)
+ pos += dictionarySize;
+ previousByte = dictionary[pos];
+ dictionary[dictionaryPos] = previousByte;
+ dictionaryPos = (dictionaryPos + 1) % dictionarySize;
+ PUT_BYTE_(previousByte);
+ len--;
+ }
+ while(len > 0);
+ }
+ mode = LZMA_C_BLOCK;
+ break;
+ case LZMA_C_RDBD:
+ _LZMA_C_RDBD:
+ {
+ UInt32 bound = (range >> kNumBitModelTotalBits) * *prob;
+ if (code < bound)
+ {
+ range = bound;
+ *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
+ bit = 0;
+ }
+ else
+ {
+ range -= bound;
+ code -= bound;
+ *prob -= (*prob) >> kNumMoveBits;
+ bit = 1;
+ }
+ RC_NORMALIZE(LZMA_C_RDBD_IN);
+ }
+ mode = last;
+ break;
+ case LZMA_C_LEND:
+ _LZMA_C_LEND:
+ DECODE_BIT(LZMA_C_LEND1, probs + LenChoice);
+ if (bit == 0)
+ {
+ len = 0;
+ probs += LenLow + (posState << kLenNumLowBits);
+ numLevels = kLenNumLowBits;
+ }
+ else {
+ DECODE_BIT(LZMA_C_LEND2, probs + LenChoice2);
+ if (bit == 0)
+ {
+ len = kLenNumLowSymbols;
+ probs += + LenMid + (posState << kLenNumMidBits);
+ numLevels = kLenNumMidBits;
+ }
+ else
+ {
+ len = kLenNumLowSymbols + kLenNumMidSymbols;
+ probs += LenHigh;
+ numLevels = kLenNumHighBits;
+ }
+ }
+
+ last3 = LZMA_C_LEND_RES;
+ case LZMA_C_BTD:
+ _LZMA_C_BTD:
+ mi = 1;
+ for(i = numLevels; i > 0; i--)
+ {
+ prob = probs + mi;
+ RC_GET_BIT(LZMA_C_BTD_LOOP, prob, mi)
+ }
+ result = mi - (1 << numLevels);
+ mode = last3;
+ break;
+ case LZMA_C_LEND_RES:
+ len += result;
+ mode = last2;
+ break;
+ default:
+ return LZMA_DATA_ERROR;
+ }
+
+saveStateAndReturn:
+
+ /* save decoder state */
+ *s = _s;
+
+ return LZMA_OK;
+}
|