Compression algo dependencies, still need hackery...

1 files changed, 1076 insertions, 0 deletions

diff --git a/depends/lzma/pavlov/LzmaDec.c b/depends/lzma/pavlov/LzmaDec.c
new file mode 100755
index 00000000..1a44dd00
--- /dev/null
+++ b/depends/lzma/pavlov/LzmaDec.c
@@ -0,0 +1,1076 @@
+/* LzmaDec.c -- LZMA Decoder
+2008-11-06 : Igor Pavlov : Public domain */
+
+#include "LzmaDec.h"
+
+#include <string.h>
+#include <stdlib.h>
+
+#define kNumTopBits 24
+#define kTopValue ((uint32_t)1 << kNumTopBits)
+
+#define kNumBitModelTotalBits 11
+#define kBitModelTotal (1 << kNumBitModelTotalBits)
+#define kNumMoveBits 5
+
+#define RC_INIT_SIZE 5
+
+#define NORMALIZE                                                                              \
+	if (range < kTopValue)                                                                     \
+	{                                                                                          \
+		range <<= 8;                                                                           \
+		code = (code << 8) | (*buf++);                                                         \
+	}
+
+#define IF_BIT_0(p)                                                                            \
+	ttt = *(p);                                                                                \
+	NORMALIZE;                                                                                 \
+	bound = (range >> kNumBitModelTotalBits) * ttt;                                            \
+	if (code < bound)
+#define UPDATE_0(p)                                                                            \
+	range = bound;                                                                             \
+	*(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
+#define UPDATE_1(p)                                                                            \
+	range -= bound;                                                                            \
+	code -= bound;                                                                             \
+	*(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
+#define GET_BIT2(p, i, A0, A1)                                                                 \
+	IF_BIT_0(p)                                                                                \
+	{                                                                                          \
+		UPDATE_0(p);                                                                           \
+		i = (i + i);                                                                           \
+		A0;                                                                                    \
+	}                                                                                          \
+	else                                                                                       \
+	{                                                                                          \
+		UPDATE_1(p);                                                                           \
+		i = (i + i) + 1;                                                                       \
+		A1;                                                                                    \
+	}
+#define GET_BIT(p, i) GET_BIT2(p, i, ;, ;)
+
+#define TREE_GET_BIT(probs, i)                                                                 \
+	{                                                                                          \
+		GET_BIT((probs + i), i);                                                               \
+	}
+#define TREE_DECODE(probs, limit, i)                                                           \
+	{                                                                                          \
+		i = 1;                                                                                 \
+		do                                                                                     \
+		{                                                                                      \
+			TREE_GET_BIT(probs, i);                                                            \
+		} while (i < limit);                                                                   \
+		i -= limit;                                                                            \
+	}
+
+/* #define _LZMA_SIZE_OPT */
+
+#ifdef _LZMA_SIZE_OPT
+#define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
+#else
+#define TREE_6_DECODE(probs, i)                                                                \
+	{                                                                                          \
+		i = 1;                                                                                 \
+		TREE_GET_BIT(probs, i);                                                                \
+		TREE_GET_BIT(probs, i);                                                                \
+		TREE_GET_BIT(probs, i);                                                                \
+		TREE_GET_BIT(probs, i);                                                                \
+		TREE_GET_BIT(probs, i);                                                                \
+		TREE_GET_BIT(probs, i);                                                                \
+		i -= 0x40;                                                                             \
+	}
+#endif
+
+#define NORMALIZE_CHECK                                                                        \
+	if (range < kTopValue)                                                                     \
+	{                                                                                          \
+		if (buf >= bufLimit)                                                                   \
+			return DUMMY_ERROR;                                                                \
+		range <<= 8;                                                                           \
+		code = (code << 8) | (*buf++);                                                         \
+	}
+
+#define IF_BIT_0_CHECK(p)                                                                      \
+	ttt = *(p);                                                                                \
+	NORMALIZE_CHECK;                                                                           \
+	bound = (range >> kNumBitModelTotalBits) * ttt;                                            \
+	if (code < bound)
+#define UPDATE_0_CHECK range = bound;
+#define UPDATE_1_CHECK                                                                         \
+	range -= bound;                                                                            \
+	code -= bound;
+#define GET_BIT2_CHECK(p, i, A0, A1)                                                           \
+	IF_BIT_0_CHECK(p)                                                                          \
+	{                                                                                          \
+		UPDATE_0_CHECK;                                                                        \
+		i = (i + i);                                                                           \
+		A0;                                                                                    \
+	}                                                                                          \
+	else                                                                                       \
+	{                                                                                          \
+		UPDATE_1_CHECK;                                                                        \
+		i = (i + i) + 1;                                                                       \
+		A1;                                                                                    \
+	}
+#define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ;, ;)
+#define TREE_DECODE_CHECK(probs, limit, i)                                                     \
+	{                                                                                          \
+		i = 1;                                                                                 \
+		do                                                                                     \
+		{                                                                                      \
+			GET_BIT_CHECK(probs + i, i)                                                        \
+		} while (i < limit);                                                                   \
+		i -= limit;                                                                            \
+	}
+
+#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 kNumLitStates 7
+
+#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 kMatchSpecLenStart                                                                     \
+	(kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
+
+#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
+
+#define LzmaProps_GetNumProbs(p)                                                               \
+	((uint32_t)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
+
+#if Literal != LZMA_BASE_SIZE
+StopCompilingDueBUG
+#endif
+	static const uint8_t kLiteralNextStates[kNumStates * 2] = {
+		0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5, 7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10};
+
+#define LZMA_DIC_MIN (1 << 12)
+
+/* First LZMA-symbol is always decoded.
+And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization
+Out:
+  Result:
+	SZ_OK - OK
+	SZ_ERROR_DATA - Error
+  p->remainLen:
+	< kMatchSpecLenStart : normal remain
+	= kMatchSpecLenStart : finished
+	= kMatchSpecLenStart + 1 : Flush marker
+	= kMatchSpecLenStart + 2 : State Init Marker
+*/
+
+static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, size_t limit, const uint8_t *bufLimit)
+{
+	CLzmaProb *probs = p->probs;
+
+	unsigned state = p->state;
+	uint32_t rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
+	unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
+	unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1;
+	unsigned lc = p->prop.lc;
+
+	uint8_t *dic = p->dic;
+	size_t dicBufSize = p->dicBufSize;
+	size_t dicPos = p->dicPos;
+
+	uint32_t processedPos = p->processedPos;
+	uint32_t checkDicSize = p->checkDicSize;
+	unsigned len = 0;
+
+	const uint8_t *buf = p->buf;
+	uint32_t range = p->range;
+	uint32_t code = p->code;
+
+	do
+	{
+		CLzmaProb *prob;
+		uint32_t bound;
+		unsigned ttt;
+		unsigned posState = processedPos & pbMask;
+
+		prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
+		IF_BIT_0(prob)
+		{
+			unsigned symbol;
+			UPDATE_0(prob);
+			prob = probs + Literal;
+			if (checkDicSize != 0 || processedPos != 0)
+				prob += (LZMA_LIT_SIZE *
+						 (((processedPos & lpMask) << lc) +
+						  (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));
+
+			if (state < kNumLitStates)
+			{
+				symbol = 1;
+				do
+				{
+					GET_BIT(prob + symbol, symbol)
+				} while (symbol < 0x100);
+			}
+			else
+			{
+				unsigned matchByte =
+					p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
+				unsigned offs = 0x100;
+				symbol = 1;
+				do
+				{
+					unsigned bit;
+					CLzmaProb *probLit;
+					matchByte <<= 1;
+					bit = (matchByte & offs);
+					probLit = prob + offs + bit + symbol;
+					GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)
+				} while (symbol < 0x100);
+			}
+			dic[dicPos++] = (uint8_t)symbol;
+			processedPos++;
+
+			state = kLiteralNextStates[state];
+			/* if (state < 4) state = 0; else if (state < 10) state -= 3; else state -= 6; */
+			continue;
+		}
+		else
+		{
+			UPDATE_1(prob);
+			prob = probs + IsRep + state;
+			IF_BIT_0(prob)
+			{
+				UPDATE_0(prob);
+				state += kNumStates;
+				prob = probs + LenCoder;
+			}
+			else
+			{
+				UPDATE_1(prob);
+				if (checkDicSize == 0 && processedPos == 0)
+					return SZ_ERROR_DATA;
+				prob = probs + IsRepG0 + state;
+				IF_BIT_0(prob)
+				{
+					UPDATE_0(prob);
+					prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
+					IF_BIT_0(prob)
+					{
+						UPDATE_0(prob);
+						dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
+						dicPos++;
+						processedPos++;
+						state = state < kNumLitStates ? 9 : 11;
+						continue;
+					}
+					UPDATE_1(prob);
+				}
+				else
+				{
+					uint32_t distance;
+					UPDATE_1(prob);
+					prob = probs + IsRepG1 + state;
+					IF_BIT_0(prob)
+					{
+						UPDATE_0(prob);
+						distance = rep1;
+					}
+					else
+					{
+						UPDATE_1(prob);
+						prob = probs + IsRepG2 + state;
+						IF_BIT_0(prob)
+						{
+							UPDATE_0(prob);
+							distance = rep2;
+						}
+						else
+						{
+							UPDATE_1(prob);
+							distance = rep3;
+							rep3 = rep2;
+						}
+						rep2 = rep1;
+					}
+					rep1 = rep0;
+					rep0 = distance;
+				}
+				state = state < kNumLitStates ? 8 : 11;
+				prob = probs + RepLenCoder;
+			}
+			{
+				unsigned limit, offset;
+				CLzmaProb *probLen = prob + LenChoice;
+				IF_BIT_0(probLen)
+				{
+					UPDATE_0(probLen);
+					probLen = prob + LenLow + (posState << kLenNumLowBits);
+					offset = 0;
+					limit = (1 << kLenNumLowBits);
+				}
+				else
+				{
+					UPDATE_1(probLen);
+					probLen = prob + LenChoice2;
+					IF_BIT_0(probLen)
+					{
+						UPDATE_0(probLen);
+						probLen = prob + LenMid + (posState << kLenNumMidBits);
+						offset = kLenNumLowSymbols;
+						limit = (1 << kLenNumMidBits);
+					}
+					else
+					{
+						UPDATE_1(probLen);
+						probLen = prob + LenHigh;
+						offset = kLenNumLowSymbols + kLenNumMidSymbols;
+						limit = (1 << kLenNumHighBits);
+					}
+				}
+				TREE_DECODE(probLen, limit, len);
+				len += offset;
+			}
+
+			if (state >= kNumStates)
+			{
+				uint32_t distance;
+				prob =
+					probs + PosSlot + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1)
+									   << kNumPosSlotBits);
+				TREE_6_DECODE(prob, distance);
+				if (distance >= kStartPosModelIndex)
+				{
+					unsigned posSlot = (unsigned)distance;
+					int numDirectBits = (int)(((distance >> 1) - 1));
+					distance = (2 | (distance & 1));
+					if (posSlot < kEndPosModelIndex)
+					{
+						distance <<= numDirectBits;
+						prob = probs + SpecPos + distance - posSlot - 1;
+						{
+							uint32_t mask = 1;
+							unsigned i = 1;
+							do
+							{
+								GET_BIT2(prob + i, i, ;, distance |= mask);
+								mask <<= 1;
+							} while (--numDirectBits != 0);
+						}
+					}
+					else
+					{
+						numDirectBits -= kNumAlignBits;
+						do
+						{
+							NORMALIZE
+							range >>= 1;
+
+							{
+								uint32_t t;
+								code -= range;
+								t = (0 -
+									 ((uint32_t)code >> 31)); /* (UInt32)((Int32)code >> 31) */
+								distance = (distance << 1) + (t + 1);
+								code += range & t;
+							}
+							/*
+							distance <<= 1;
+							if (code >= range)
+							{
+							  code -= range;
+							  distance |= 1;
+							}
+							*/
+						} while (--numDirectBits != 0);
+						prob = probs + Align;
+						distance <<= kNumAlignBits;
+						{
+							unsigned i = 1;
+							GET_BIT2(prob + i, i, ;, distance |= 1);
+							GET_BIT2(prob + i, i, ;, distance |= 2);
+							GET_BIT2(prob + i, i, ;, distance |= 4);
+							GET_BIT2(prob + i, i, ;, distance |= 8);
+						}
+						if (distance == (uint32_t)0xFFFFFFFF)
+						{
+							len += kMatchSpecLenStart;
+							state -= kNumStates;
+							break;
+						}
+					}
+				}
+				rep3 = rep2;
+				rep2 = rep1;
+				rep1 = rep0;
+				rep0 = distance + 1;
+				if (checkDicSize == 0)
+				{
+					if (distance >= processedPos)
+						return SZ_ERROR_DATA;
+				}
+				else if (distance >= checkDicSize)
+					return SZ_ERROR_DATA;
+				state =
+					(state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
+				/* state = kLiteralNextStates[state]; */
+			}
+
+			len += kMatchMinLen;
+
+			if (limit == dicPos)
+				return SZ_ERROR_DATA;
+			{
+				size_t rem = limit - dicPos;
+				unsigned curLen = ((rem < len) ? (unsigned)rem : len);
+				size_t pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
+
+				processedPos += curLen;
+
+				len -= curLen;
+				if (pos + curLen <= dicBufSize)
+				{
+					uint8_t *dest = dic + dicPos;
+					ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
+					const uint8_t *lim = dest + curLen;
+					dicPos += curLen;
+					do
+						*(dest) = (uint8_t) * (dest + src);
+					while (++dest != lim);
+				}
+				else
+				{
+					do
+					{
+						dic[dicPos++] = dic[pos];
+						if (++pos == dicBufSize)
+							pos = 0;
+					} while (--curLen != 0);
+				}
+			}
+		}
+	} while (dicPos < limit && buf < bufLimit);
+	NORMALIZE;
+	p->buf = buf;
+	p->range = range;
+	p->code = code;
+	p->remainLen = len;
+	p->dicPos = dicPos;
+	p->processedPos = processedPos;
+	p->reps[0] = rep0;
+	p->reps[1] = rep1;
+	p->reps[2] = rep2;
+	p->reps[3] = rep3;
+	p->state = state;
+
+	return SZ_OK;
+}
+
+static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, size_t limit)
+{
+	if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
+	{
+		uint8_t *dic = p->dic;
+		size_t dicPos = p->dicPos;
+		size_t dicBufSize = p->dicBufSize;
+		unsigned len = p->remainLen;
+		uint32_t rep0 = p->reps[0];
+		if (limit - dicPos < len)
+			len = (unsigned)(limit - dicPos);
+
+		if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
+			p->checkDicSize = p->prop.dicSize;
+
+		p->processedPos += len;
+		p->remainLen -= len;
+		while (len-- != 0)
+		{
+			dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
+			dicPos++;
+		}
+		p->dicPos = dicPos;
+	}
+}
+
+static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, size_t limit, const uint8_t *bufLimit)
+{
+	do
+	{
+		size_t limit2 = limit;
+		if (p->checkDicSize == 0)
+		{
+			uint32_t rem = p->prop.dicSize - p->processedPos;
+			if (limit - p->dicPos > rem)
+				limit2 = p->dicPos + rem;
+		}
+		RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));
+		if (p->processedPos >= p->prop.dicSize)
+			p->checkDicSize = p->prop.dicSize;
+		LzmaDec_WriteRem(p, limit);
+	} while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
+
+	if (p->remainLen > kMatchSpecLenStart)
+	{
+		p->remainLen = kMatchSpecLenStart;
+	}
+	return 0;
+}
+
+typedef enum
+{
+	DUMMY_ERROR, /* unexpected end of input stream */
+	DUMMY_LIT,
+	DUMMY_MATCH,
+	DUMMY_REP
+} ELzmaDummy;
+
+static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const uint8_t *buf, size_t inSize)
+{
+	uint32_t range = p->range;
+	uint32_t code = p->code;
+	const uint8_t *bufLimit = buf + inSize;
+	CLzmaProb *probs = p->probs;
+	unsigned state = p->state;
+	ELzmaDummy res;
+
+	{
+		CLzmaProb *prob;
+		uint32_t bound;
+		unsigned ttt;
+		unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);
+
+		prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
+		IF_BIT_0_CHECK(prob)
+		{
+			UPDATE_0_CHECK
+
+			/* if (bufLimit - buf >= 7) return DUMMY_LIT; */
+
+			prob = probs + Literal;
+			if (p->checkDicSize != 0 || p->processedPos != 0)
+				prob += (LZMA_LIT_SIZE *
+						 ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
+						  (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >>
+						   (8 - p->prop.lc))));
+
+			if (state < kNumLitStates)
+			{
+				unsigned symbol = 1;
+				do
+				{
+					GET_BIT_CHECK(prob + symbol, symbol)
+				} while (symbol < 0x100);
+			}
+			else
+			{
+				unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
+											((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)];
+				unsigned offs = 0x100;
+				unsigned symbol = 1;
+				do
+				{
+					unsigned bit;
+					CLzmaProb *probLit;
+					matchByte <<= 1;
+					bit = (matchByte & offs);
+					probLit = prob + offs + bit + symbol;
+					GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)
+				} while (symbol < 0x100);
+			}
+			res = DUMMY_LIT;
+		}
+		else
+		{
+			unsigned len;
+			UPDATE_1_CHECK;
+
+			prob = probs + IsRep + state;
+			IF_BIT_0_CHECK(prob)
+			{
+				UPDATE_0_CHECK;
+				state = 0;
+				prob = probs + LenCoder;
+				res = DUMMY_MATCH;
+			}
+			else
+			{
+				UPDATE_1_CHECK;
+				res = DUMMY_REP;
+				prob = probs + IsRepG0 + state;
+				IF_BIT_0_CHECK(prob)
+				{
+					UPDATE_0_CHECK;
+					prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
+					IF_BIT_0_CHECK(prob)
+					{
+						UPDATE_0_CHECK;
+						NORMALIZE_CHECK;
+						return DUMMY_REP;
+					}
+					else
+					{
+						UPDATE_1_CHECK;
+					}
+				}
+				else
+				{
+					UPDATE_1_CHECK;
+					prob = probs + IsRepG1 + state;
+					IF_BIT_0_CHECK(prob)
+					{
+						UPDATE_0_CHECK;
+					}
+					else
+					{
+						UPDATE_1_CHECK;
+						prob = probs + IsRepG2 + state;
+						IF_BIT_0_CHECK(prob)
+						{
+							UPDATE_0_CHECK;
+						}
+						else
+						{
+							UPDATE_1_CHECK;
+						}
+					}
+				}
+				state = kNumStates;
+				prob = probs + RepLenCoder;
+			}
+			{
+				unsigned limit, offset;
+				CLzmaProb *probLen = prob + LenChoice;
+				IF_BIT_0_CHECK(probLen)
+				{
+					UPDATE_0_CHECK;
+					probLen = prob + LenLow + (posState << kLenNumLowBits);
+					offset = 0;
+					limit = 1 << kLenNumLowBits;
+				}
+				else
+				{
+					UPDATE_1_CHECK;
+					probLen = prob + LenChoice2;
+					IF_BIT_0_CHECK(probLen)
+					{
+						UPDATE_0_CHECK;
+						probLen = prob + LenMid + (posState << kLenNumMidBits);
+						offset = kLenNumLowSymbols;
+						limit = 1 << kLenNumMidBits;
+					}
+					else
+					{
+						UPDATE_1_CHECK;
+						probLen = prob + LenHigh;
+						offset = kLenNumLowSymbols + kLenNumMidSymbols;
+						limit = 1 << kLenNumHighBits;
+					}
+				}
+				TREE_DECODE_CHECK(probLen, limit, len);
+				len += offset;
+			}
+
+			if (state < 4)
+			{
+				unsigned posSlot;
+				prob =
+					probs + PosSlot + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1)
+									   << kNumPosSlotBits);
+				TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
+				if (posSlot >= kStartPosModelIndex)
+				{
+					int numDirectBits = ((posSlot >> 1) - 1);
+
+					/* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
+
+					if (posSlot < kEndPosModelIndex)
+					{
+						prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) -
+							   posSlot - 1;
+					}
+					else
+					{
+						numDirectBits -= kNumAlignBits;
+						do
+						{
+							NORMALIZE_CHECK
+							range >>= 1;
+							code -= range & (((code - range) >> 31) - 1);
+							/* if (code >= range) code -= range; */
+						} while (--numDirectBits != 0);
+						prob = probs + Align;
+						numDirectBits = kNumAlignBits;
+					}
+					{
+						unsigned i = 1;
+						do
+						{
+							GET_BIT_CHECK(prob + i, i);
+						} while (--numDirectBits != 0);
+					}
+				}
+			}
+		}
+	}
+	NORMALIZE_CHECK;
+	return res;
+}
+
+static void LzmaDec_InitRc(CLzmaDec *p, const uint8_t *data)
+{
+	p->code = ((uint32_t)data[1] << 24) | ((uint32_t)data[2] << 16) | ((uint32_t)data[3] << 8) |
+			  ((uint32_t)data[4]);
+	p->range = 0xFFFFFFFF;
+	p->needFlush = 0;
+}
+
+void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)
+{
+	p->needFlush = 1;
+	p->remainLen = 0;
+	p->tempBufSize = 0;
+
+	if (initDic)
+	{
+		p->processedPos = 0;
+		p->checkDicSize = 0;
+		p->needInitState = 1;
+	}
+	if (initState)
+		p->needInitState = 1;
+}
+
+void LzmaDec_Init(CLzmaDec *p)
+{
+	p->dicPos = 0;
+	LzmaDec_InitDicAndState(p, True, True);
+}
+
+static void LzmaDec_InitStateReal(CLzmaDec *p)
+{
+	uint32_t numProbs = Literal + ((uint32_t)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
+	uint32_t i;
+	CLzmaProb *probs = p->probs;
+	for (i = 0; i < numProbs; i++)
+		probs[i] = kBitModelTotal >> 1;
+	p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
+	p->state = 0;
+	p->needInitState = 0;
+}
+
+SRes LzmaDec_DecodeToDic(CLzmaDec *p, size_t dicLimit, const uint8_t *src, size_t *srcLen,
+						 ELzmaFinishMode finishMode, ELzmaStatus *status)
+{
+	size_t inSize = *srcLen;
+	(*srcLen) = 0;
+	LzmaDec_WriteRem(p, dicLimit);
+
+	*status = LZMA_STATUS_NOT_SPECIFIED;
+
+	while (p->remainLen != kMatchSpecLenStart)
+	{
+		int checkEndMarkNow;
+
+		if (p->needFlush != 0)
+		{
+			for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
+				p->tempBuf[p->tempBufSize++] = *src++;
+			if (p->tempBufSize < RC_INIT_SIZE)
+			{
+				*status = LZMA_STATUS_NEEDS_MORE_INPUT;
+				return SZ_OK;
+			}
+			if (p->tempBuf[0] != 0)
+				return SZ_ERROR_DATA;
+
+			LzmaDec_InitRc(p, p->tempBuf);
+			p->tempBufSize = 0;
+		}
+
+		checkEndMarkNow = 0;
+		if (p->dicPos >= dicLimit)
+		{
+			if (p->remainLen == 0 && p->code == 0)
+			{
+				*status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
+				return SZ_OK;
+			}
+			if (finishMode == LZMA_FINISH_ANY)
+			{
+				*status = LZMA_STATUS_NOT_FINISHED;
+				return SZ_OK;
+			}
+			if (p->remainLen != 0)
+			{
+				*status = LZMA_STATUS_NOT_FINISHED;
+				return SZ_ERROR_DATA;
+			}
+			checkEndMarkNow = 1;
+		}
+
+		if (p->needInitState)
+			LzmaDec_InitStateReal(p);
+
+		if (p->tempBufSize == 0)
+		{
+			size_t processed;
+			const uint8_t *bufLimit;
+			if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
+			{
+				int dummyRes = LzmaDec_TryDummy(p, src, inSize);
+				if (dummyRes == DUMMY_ERROR)
+				{
+					memcpy(p->tempBuf, src, inSize);
+					p->tempBufSize = (unsigned)inSize;
+					(*srcLen) += inSize;
+					*status = LZMA_STATUS_NEEDS_MORE_INPUT;
+					return SZ_OK;
+				}
+				if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
+				{
+					*status = LZMA_STATUS_NOT_FINISHED;
+					return SZ_ERROR_DATA;
+				}
+				bufLimit = src;
+			}
+			else
+				bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
+			p->buf = src;
+			if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
+				return SZ_ERROR_DATA;
+			processed = (size_t)(p->buf - src);
+			(*srcLen) += processed;
+			src += processed;
+			inSize -= processed;
+		}
+		else
+		{
+			unsigned rem = p->tempBufSize, lookAhead = 0;
+			while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
+				p->tempBuf[rem++] = src[lookAhead++];
+			p->tempBufSize = rem;
+			if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
+			{
+				int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
+				if (dummyRes == DUMMY_ERROR)
+				{
+					(*srcLen) += lookAhead;
+					*status = LZMA_STATUS_NEEDS_MORE_INPUT;
+					return SZ_OK;
+				}
+				if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
+				{
+					*status = LZMA_STATUS_NOT_FINISHED;
+					return SZ_ERROR_DATA;
+				}
+			}
+			p->buf = p->tempBuf;
+			if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
+				return SZ_ERROR_DATA;
+			lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));
+			(*srcLen) += lookAhead;
+			src += lookAhead;
+			inSize -= lookAhead;
+			p->tempBufSize = 0;
+		}
+	}
+	if (p->code == 0)
+		*status = LZMA_STATUS_FINISHED_WITH_MARK;
+	return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;
+}
+
+SRes LzmaDec_DecodeToBuf(CLzmaDec *p, uint8_t *dest, size_t *destLen, const uint8_t *src,
+						 size_t *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
+{
+	size_t outSize = *destLen;
+	size_t inSize = *srcLen;
+	*srcLen = *destLen = 0;
+	for (;;)
+	{
+		size_t inSizeCur = inSize, outSizeCur, dicPos;
+		ELzmaFinishMode curFinishMode;
+		SRes res;
+		if (p->dicPos == p->dicBufSize)
+			p->dicPos = 0;
+		dicPos = p->dicPos;
+		if (outSize > p->dicBufSize - dicPos)
+		{
+			outSizeCur = p->dicBufSize;
+			curFinishMode = LZMA_FINISH_ANY;
+		}
+		else
+		{
+			outSizeCur = dicPos + outSize;
+			curFinishMode = finishMode;
+		}
+
+		res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
+		src += inSizeCur;
+		inSize -= inSizeCur;
+		*srcLen += inSizeCur;
+		outSizeCur = p->dicPos - dicPos;
+		memcpy(dest, p->dic + dicPos, outSizeCur);
+		dest += outSizeCur;
+		outSize -= outSizeCur;
+		*destLen += outSizeCur;
+		if (res != 0)
+			return res;
+		if (outSizeCur == 0 || outSize == 0)
+			return SZ_OK;
+	}
+}
+
+void LzmaDec_FreeProbs(CLzmaDec *p)
+{
+	free(p->probs);
+	p->probs = 0;
+}
+
+static void LzmaDec_FreeDict(CLzmaDec *p)
+{
+	free(p->dic);
+	p->dic = 0;
+}
+
+void LzmaDec_Free(CLzmaDec *p)
+{
+	LzmaDec_FreeProbs(p);
+	LzmaDec_FreeDict(p);
+}
+
+SRes LzmaProps_Decode(CLzmaProps *p, const uint8_t *data, unsigned size)
+{
+	uint32_t dicSize;
+	uint8_t d;
+
+	if (size < LZMA_PROPS_SIZE)
+		return SZ_ERROR_UNSUPPORTED;
+	else
+		dicSize = data[1] | ((uint32_t)data[2] << 8) | ((uint32_t)data[3] << 16) |
+				  ((uint32_t)data[4] << 24);
+
+	if (dicSize < LZMA_DIC_MIN)
+		dicSize = LZMA_DIC_MIN;
+	p->dicSize = dicSize;
+
+	d = data[0];
+	if (d >= (9 * 5 * 5))
+		return SZ_ERROR_UNSUPPORTED;
+
+	p->lc = d % 9;
+	d /= 9;
+	p->pb = d / 5;
+	p->lp = d % 5;
+
+	return SZ_OK;
+}
+
+static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew)
+{
+	uint32_t numProbs = LzmaProps_GetNumProbs(propNew);
+	if (p->probs == 0 || numProbs != p->numProbs)
+	{
+		LzmaDec_FreeProbs(p);
+		p->probs = (CLzmaProb *)malloc(numProbs * sizeof(CLzmaProb));
+		p->numProbs = numProbs;
+		if (p->probs == 0)
+			return SZ_ERROR_MEM;
+	}
+	return SZ_OK;
+}
+
+SRes LzmaDec_AllocateProbs(CLzmaDec *p, const uint8_t *props, unsigned propsSize)
+{
+	CLzmaProps propNew;
+	RINOK(LzmaProps_Decode(&propNew, props, propsSize));
+	RINOK(LzmaDec_AllocateProbs2(p, &propNew));
+	p->prop = propNew;
+	return SZ_OK;
+}
+
+SRes LzmaDec_Allocate(CLzmaDec *p, const uint8_t *props, unsigned propsSize)
+{
+	CLzmaProps propNew;
+	size_t dicBufSize;
+	RINOK(LzmaProps_Decode(&propNew, props, propsSize));
+	RINOK(LzmaDec_AllocateProbs2(p, &propNew));
+	dicBufSize = propNew.dicSize;
+	if (p->dic == 0 || dicBufSize != p->dicBufSize)
+	{
+		LzmaDec_FreeDict(p);
+		p->dic = (uint8_t *)malloc(dicBufSize);
+		if (p->dic == 0)
+		{
+			LzmaDec_FreeProbs(p);
+			return SZ_ERROR_MEM;
+		}
+	}
+	p->dicBufSize = dicBufSize;
+	p->prop = propNew;
+	return SZ_OK;
+}
+
+SRes LzmaDecode(uint8_t *dest, size_t *destLen, const uint8_t *src, size_t *srcLen,
+				const uint8_t *propData, unsigned propSize, ELzmaFinishMode finishMode,
+				ELzmaStatus *status)
+{
+	CLzmaDec p;
+	SRes res;
+	size_t inSize = *srcLen;
+	size_t outSize = *destLen;
+	*srcLen = *destLen = 0;
+	if (inSize < RC_INIT_SIZE)
+		return SZ_ERROR_INPUT_EOF;
+
+	LzmaDec_Construct(&p);
+	res = LzmaDec_AllocateProbs(&p, propData, propSize);
+	if (res != 0)
+		return res;
+	p.dic = dest;
+	p.dicBufSize = outSize;
+
+	LzmaDec_Init(&p);
+
+	*srcLen = inSize;
+	res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
+
+	if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
+		res = SZ_ERROR_INPUT_EOF;
+
+	(*destLen) = p.dicPos;
+	LzmaDec_FreeProbs(&p);
+	return res;
+}