/*
* LZMADecode.c
*
* This file is a part of LZMA compression module for NSIS.
*
* Original LZMA SDK Copyright (C) 1999-2006 Igor Pavlov
* Modifications Copyright (C) 2003-2007 Amir Szekely <kichik@netvision.net.il>
*
* Licensed under the Common Public License version 1.0 (the "License");
* you may not use this file except in compliance with the License.
*
* Licence details can be found in the file COPYING.nsis.
*
* This software is provided 'as-is', without any express or implied
* warranty.
*/
#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 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--)
((lzByte *)s)[i] = 0;
s->rep0 = s->rep1 = s->rep2 = s->rep3 = 1;
s->range = (0xFFFFFFFF);
}
int 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:
{
lzByte 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;
}
/* aCaB */
void lzmaShutdown(lzma_stream *s) {
lzma_stream _s = *s;
if (p) lzmafree(p);
if (dictionary) lzmafree(dictionary);
p = NULL;
dictionary = NULL;
*s = _s;
}