summaryrefslogtreecommitdiff
path: root/lib/lzma
diff options
context:
space:
mode:
authorPeter Tyser <ptyser@xes-inc.com>2010-04-12 22:28:05 -0500
committerWolfgang Denk <wd@denx.de>2010-04-13 09:13:04 +0200
commit78acc472d9719316f22e002a009a998d9ceec29d (patch)
treeaa99461b3d693cf3691869abea485091860a66d0 /lib/lzma
parentea0364f1bbfed1e3ea711147420875cf338fe77a (diff)
Rename lib_generic/ to lib/
Now that the other architecture-specific lib directories have been moved out of the top-level directory there's not much reason to have the '_generic' suffix on the common lib directory. Signed-off-by: Peter Tyser <ptyser@xes-inc.com>
Diffstat (limited to 'lib/lzma')
-rw-r--r--lib/lzma/LzmaDec.c1033
-rw-r--r--lib/lzma/LzmaDec.h223
-rw-r--r--lib/lzma/LzmaTools.c133
-rw-r--r--lib/lzma/LzmaTools.h35
-rw-r--r--lib/lzma/Makefile51
-rw-r--r--lib/lzma/README.txt28
-rw-r--r--lib/lzma/Types.h208
-rw-r--r--lib/lzma/history.txt236
-rw-r--r--lib/lzma/import_lzmasdk.sh36
-rw-r--r--lib/lzma/license.txt3
-rw-r--r--lib/lzma/lzma.txt594
11 files changed, 2580 insertions, 0 deletions
diff --git a/lib/lzma/LzmaDec.c b/lib/lzma/LzmaDec.c
new file mode 100644
index 00000000000..f941da27dd0
--- /dev/null
+++ b/lib/lzma/LzmaDec.c
@@ -0,0 +1,1033 @@
+/* LzmaDec.c -- LZMA Decoder
+2008-11-06 : Igor Pavlov : Public domain */
+
+#include <config.h>
+#include <common.h>
+#include <watchdog.h>
+#include "LzmaDec.h"
+
+#include <linux/string.h>
+
+#define kNumTopBits 24
+#define kTopValue ((UInt32)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)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
+
+#if Literal != LZMA_BASE_SIZE
+StopCompilingDueBUG
+#endif
+
+static const Byte 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, SizeT limit, const Byte *bufLimit)
+{
+ CLzmaProb *probs = p->probs;
+
+ unsigned state = p->state;
+ UInt32 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;
+
+ Byte *dic = p->dic;
+ SizeT dicBufSize = p->dicBufSize;
+ SizeT dicPos = p->dicPos;
+
+ UInt32 processedPos = p->processedPos;
+ UInt32 checkDicSize = p->checkDicSize;
+ unsigned len = 0;
+
+ const Byte *buf = p->buf;
+ UInt32 range = p->range;
+ UInt32 code = p->code;
+
+ WATCHDOG_RESET();
+
+ do
+ {
+ CLzmaProb *prob;
+ UInt32 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;
+
+ WATCHDOG_RESET();
+
+ 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;
+
+ WATCHDOG_RESET();
+
+ 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++] = (Byte)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 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 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 mask = 1;
+ unsigned i = 1;
+
+ WATCHDOG_RESET();
+
+ do
+ {
+ GET_BIT2(prob + i, i, ; , distance |= mask);
+ mask <<= 1;
+ }
+ while (--numDirectBits != 0);
+ }
+ }
+ else
+ {
+ numDirectBits -= kNumAlignBits;
+
+ WATCHDOG_RESET();
+
+ do
+ {
+ NORMALIZE
+ range >>= 1;
+
+ {
+ UInt32 t;
+ code -= range;
+ t = (0 - ((UInt32)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)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;
+ {
+ SizeT rem = limit - dicPos;
+ unsigned curLen = ((rem < len) ? (unsigned)rem : len);
+ SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
+
+ processedPos += curLen;
+
+ len -= curLen;
+ if (pos + curLen <= dicBufSize)
+ {
+ Byte *dest = dic + dicPos;
+ ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
+ const Byte *lim = dest + curLen;
+ dicPos += curLen;
+
+ WATCHDOG_RESET();
+
+ do
+ *(dest) = (Byte)*(dest + src);
+ while (++dest != lim);
+ }
+ else
+ {
+
+ WATCHDOG_RESET();
+
+ do
+ {
+ dic[dicPos++] = dic[pos];
+ if (++pos == dicBufSize)
+ pos = 0;
+ }
+ while (--curLen != 0);
+ }
+ }
+ }
+ }
+ while (dicPos < limit && buf < bufLimit);
+
+ WATCHDOG_RESET();
+
+ 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, SizeT limit)
+{
+ if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
+ {
+ Byte *dic = p->dic;
+ SizeT dicPos = p->dicPos;
+ SizeT dicBufSize = p->dicBufSize;
+ unsigned len = p->remainLen;
+ UInt32 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, SizeT limit, const Byte *bufLimit)
+{
+ do
+ {
+ SizeT limit2 = limit;
+ if (p->checkDicSize == 0)
+ {
+ UInt32 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 Byte *buf, SizeT inSize)
+{
+ UInt32 range = p->range;
+ UInt32 code = p->code;
+ const Byte *bufLimit = buf + inSize;
+ CLzmaProb *probs = p->probs;
+ unsigned state = p->state;
+ ELzmaDummy res;
+
+ {
+ CLzmaProb *prob;
+ UInt32 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 Byte *data)
+{
+ p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)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 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
+ UInt32 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, SizeT dicLimit, const Byte *src, SizeT *srcLen,
+ ELzmaFinishMode finishMode, ELzmaStatus *status)
+{
+ SizeT 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)
+ {
+ SizeT processed;
+ const Byte *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 = (SizeT)(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, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
+{
+ SizeT outSize = *destLen;
+ SizeT inSize = *srcLen;
+ *srcLen = *destLen = 0;
+ for (;;)
+ {
+ SizeT 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, ISzAlloc *alloc)
+{
+ alloc->Free(alloc, p->probs);
+ p->probs = 0;
+}
+
+static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)
+{
+ alloc->Free(alloc, p->dic);
+ p->dic = 0;
+}
+
+void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)
+{
+ LzmaDec_FreeProbs(p, alloc);
+ LzmaDec_FreeDict(p, alloc);
+}
+
+SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
+{
+ UInt32 dicSize;
+ Byte d;
+
+ if (size < LZMA_PROPS_SIZE)
+ return SZ_ERROR_UNSUPPORTED;
+ else
+ dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)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, ISzAlloc *alloc)
+{
+ UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
+ if (p->probs == 0 || numProbs != p->numProbs)
+ {
+ LzmaDec_FreeProbs(p, alloc);
+ p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));
+ p->numProbs = numProbs;
+ if (p->probs == 0)
+ return SZ_ERROR_MEM;
+ }
+ return SZ_OK;
+}
+
+SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
+{
+ CLzmaProps propNew;
+ RINOK(LzmaProps_Decode(&propNew, props, propsSize));
+ RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
+ p->prop = propNew;
+ return SZ_OK;
+}
+
+SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
+{
+ CLzmaProps propNew;
+ SizeT dicBufSize;
+ RINOK(LzmaProps_Decode(&propNew, props, propsSize));
+ RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
+ dicBufSize = propNew.dicSize;
+ if (p->dic == 0 || dicBufSize != p->dicBufSize)
+ {
+ LzmaDec_FreeDict(p, alloc);
+ p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);
+ if (p->dic == 0)
+ {
+ LzmaDec_FreeProbs(p, alloc);
+ return SZ_ERROR_MEM;
+ }
+ }
+ p->dicBufSize = dicBufSize;
+ p->prop = propNew;
+ return SZ_OK;
+}
+
+SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
+ const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
+ ELzmaStatus *status, ISzAlloc *alloc)
+{
+ CLzmaDec p;
+ SRes res;
+ SizeT inSize = *srcLen;
+ SizeT outSize = *destLen;
+ *srcLen = *destLen = 0;
+ if (inSize < RC_INIT_SIZE)
+ return SZ_ERROR_INPUT_EOF;
+
+ LzmaDec_Construct(&p);
+ res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc);
+ 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, alloc);
+ return res;
+}
diff --git a/lib/lzma/LzmaDec.h b/lib/lzma/LzmaDec.h
new file mode 100644
index 00000000000..7fba87f076e
--- /dev/null
+++ b/lib/lzma/LzmaDec.h
@@ -0,0 +1,223 @@
+/* LzmaDec.h -- LZMA Decoder
+2008-10-04 : Igor Pavlov : Public domain */
+
+#ifndef __LZMADEC_H
+#define __LZMADEC_H
+
+#include "Types.h"
+
+/* #define _LZMA_PROB32 */
+/* _LZMA_PROB32 can increase the speed on some CPUs,
+ but memory usage for CLzmaDec::probs will be doubled in that case */
+
+#ifdef _LZMA_PROB32
+#define CLzmaProb UInt32
+#else
+#define CLzmaProb UInt16
+#endif
+
+
+/* ---------- LZMA Properties ---------- */
+
+#define LZMA_PROPS_SIZE 5
+
+typedef struct _CLzmaProps
+{
+ unsigned lc, lp, pb;
+ UInt32 dicSize;
+} CLzmaProps;
+
+/* LzmaProps_Decode - decodes properties
+Returns:
+ SZ_OK
+ SZ_ERROR_UNSUPPORTED - Unsupported properties
+*/
+
+SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size);
+
+
+/* ---------- LZMA Decoder state ---------- */
+
+/* LZMA_REQUIRED_INPUT_MAX = number of required input bytes for worst case.
+ Num bits = log2((2^11 / 31) ^ 22) + 26 < 134 + 26 = 160; */
+
+#define LZMA_REQUIRED_INPUT_MAX 20
+
+typedef struct
+{
+ CLzmaProps prop;
+ CLzmaProb *probs;
+ Byte *dic;
+ const Byte *buf;
+ UInt32 range, code;
+ SizeT dicPos;
+ SizeT dicBufSize;
+ UInt32 processedPos;
+ UInt32 checkDicSize;
+ unsigned state;
+ UInt32 reps[4];
+ unsigned remainLen;
+ int needFlush;
+ int needInitState;
+ UInt32 numProbs;
+ unsigned tempBufSize;
+ Byte tempBuf[LZMA_REQUIRED_INPUT_MAX];
+} CLzmaDec;
+
+#define LzmaDec_Construct(p) { (p)->dic = 0; (p)->probs = 0; }
+
+void LzmaDec_Init(CLzmaDec *p);
+
+/* There are two types of LZMA streams:
+ 0) Stream with end mark. That end mark adds about 6 bytes to compressed size.
+ 1) Stream without end mark. You must know exact uncompressed size to decompress such stream. */
+
+typedef enum
+{
+ LZMA_FINISH_ANY, /* finish at any point */
+ LZMA_FINISH_END /* block must be finished at the end */
+} ELzmaFinishMode;
+
+/* ELzmaFinishMode has meaning only if the decoding reaches output limit !!!
+
+ You must use LZMA_FINISH_END, when you know that current output buffer
+ covers last bytes of block. In other cases you must use LZMA_FINISH_ANY.
+
+ If LZMA decoder sees end marker before reaching output limit, it returns SZ_OK,
+ and output value of destLen will be less than output buffer size limit.
+ You can check status result also.
+
+ You can use multiple checks to test data integrity after full decompression:
+ 1) Check Result and "status" variable.
+ 2) Check that output(destLen) = uncompressedSize, if you know real uncompressedSize.
+ 3) Check that output(srcLen) = compressedSize, if you know real compressedSize.
+ You must use correct finish mode in that case. */
+
+typedef enum
+{
+ LZMA_STATUS_NOT_SPECIFIED, /* use main error code instead */
+ LZMA_STATUS_FINISHED_WITH_MARK, /* stream was finished with end mark. */
+ LZMA_STATUS_NOT_FINISHED, /* stream was not finished */
+ LZMA_STATUS_NEEDS_MORE_INPUT, /* you must provide more input bytes */
+ LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK /* there is probability that stream was finished without end mark */
+} ELzmaStatus;
+
+/* ELzmaStatus is used only as output value for function call */
+
+
+/* ---------- Interfaces ---------- */
+
+/* There are 3 levels of interfaces:
+ 1) Dictionary Interface
+ 2) Buffer Interface
+ 3) One Call Interface
+ You can select any of these interfaces, but don't mix functions from different
+ groups for same object. */
+
+
+/* There are two variants to allocate state for Dictionary Interface:
+ 1) LzmaDec_Allocate / LzmaDec_Free
+ 2) LzmaDec_AllocateProbs / LzmaDec_FreeProbs
+ You can use variant 2, if you set dictionary buffer manually.
+ For Buffer Interface you must always use variant 1.
+
+LzmaDec_Allocate* can return:
+ SZ_OK
+ SZ_ERROR_MEM - Memory allocation error
+ SZ_ERROR_UNSUPPORTED - Unsupported properties
+*/
+
+SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc);
+void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc);
+
+SRes LzmaDec_Allocate(CLzmaDec *state, const Byte *prop, unsigned propsSize, ISzAlloc *alloc);
+void LzmaDec_Free(CLzmaDec *state, ISzAlloc *alloc);
+
+/* ---------- Dictionary Interface ---------- */
+
+/* You can use it, if you want to eliminate the overhead for data copying from
+ dictionary to some other external buffer.
+ You must work with CLzmaDec variables directly in this interface.
+
+ STEPS:
+ LzmaDec_Constr()
+ LzmaDec_Allocate()
+ for (each new stream)
+ {
+ LzmaDec_Init()
+ while (it needs more decompression)
+ {
+ LzmaDec_DecodeToDic()
+ use data from CLzmaDec::dic and update CLzmaDec::dicPos
+ }
+ }
+ LzmaDec_Free()
+*/
+
+/* LzmaDec_DecodeToDic
+
+ The decoding to internal dictionary buffer (CLzmaDec::dic).
+ You must manually update CLzmaDec::dicPos, if it reaches CLzmaDec::dicBufSize !!!
+
+finishMode:
+ It has meaning only if the decoding reaches output limit (dicLimit).
+ LZMA_FINISH_ANY - Decode just dicLimit bytes.
+ LZMA_FINISH_END - Stream must be finished after dicLimit.
+
+Returns:
+ SZ_OK
+ status:
+ LZMA_STATUS_FINISHED_WITH_MARK
+ LZMA_STATUS_NOT_FINISHED
+ LZMA_STATUS_NEEDS_MORE_INPUT
+ LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK
+ SZ_ERROR_DATA - Data error
+*/
+
+SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit,
+ const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status);
+
+
+/* ---------- Buffer Interface ---------- */
+
+/* It's zlib-like interface.
+ See LzmaDec_DecodeToDic description for information about STEPS and return results,
+ but you must use LzmaDec_DecodeToBuf instead of LzmaDec_DecodeToDic and you don't need
+ to work with CLzmaDec variables manually.
+
+finishMode:
+ It has meaning only if the decoding reaches output limit (*destLen).
+ LZMA_FINISH_ANY - Decode just destLen bytes.
+ LZMA_FINISH_END - Stream must be finished after (*destLen).
+*/
+
+SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen,
+ const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status);
+
+
+/* ---------- One Call Interface ---------- */
+
+/* LzmaDecode
+
+finishMode:
+ It has meaning only if the decoding reaches output limit (*destLen).
+ LZMA_FINISH_ANY - Decode just destLen bytes.
+ LZMA_FINISH_END - Stream must be finished after (*destLen).
+
+Returns:
+ SZ_OK
+ status:
+ LZMA_STATUS_FINISHED_WITH_MARK
+ LZMA_STATUS_NOT_FINISHED
+ LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK
+ SZ_ERROR_DATA - Data error
+ SZ_ERROR_MEM - Memory allocation error
+ SZ_ERROR_UNSUPPORTED - Unsupported properties
+ SZ_ERROR_INPUT_EOF - It needs more bytes in input buffer (src).
+*/
+
+SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
+ const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
+ ELzmaStatus *status, ISzAlloc *alloc);
+
+#endif
diff --git a/lib/lzma/LzmaTools.c b/lib/lzma/LzmaTools.c
new file mode 100644
index 00000000000..8860bfbf3da
--- /dev/null
+++ b/lib/lzma/LzmaTools.c
@@ -0,0 +1,133 @@
+/*
+ * Usefuls routines based on the LzmaTest.c file from LZMA SDK 4.65
+ *
+ * Copyright (C) 2007-2009 Industrie Dial Face S.p.A.
+ * Luigi 'Comio' Mantellini (luigi.mantellini@idf-hit.com)
+ *
+ * Copyright (C) 1999-2005 Igor Pavlov
+ *
+ * See file CREDITS for list of people who contributed to this
+ * project.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
+ * MA 02111-1307 USA
+ */
+
+/*
+ * LZMA_Alone stream format:
+ *
+ * uchar Properties[5]
+ * uint64 Uncompressed size
+ * uchar data[*]
+ *
+ */
+
+#include <config.h>
+#include <common.h>
+#include <watchdog.h>
+
+#ifdef CONFIG_LZMA
+
+#define LZMA_PROPERTIES_OFFSET 0
+#define LZMA_SIZE_OFFSET LZMA_PROPS_SIZE
+#define LZMA_DATA_OFFSET LZMA_SIZE_OFFSET+sizeof(uint64_t)
+
+#include "LzmaTools.h"
+#include "LzmaDec.h"
+
+#include <linux/string.h>
+#include <malloc.h>
+
+static void *SzAlloc(void *p, size_t size) { p = p; return malloc(size); }
+static void SzFree(void *p, void *address) { p = p; free(address); }
+
+int lzmaBuffToBuffDecompress (unsigned char *outStream, SizeT *uncompressedSize,
+ unsigned char *inStream, SizeT length)
+{
+ int res = SZ_ERROR_DATA;
+ int i;
+ ISzAlloc g_Alloc;
+
+ SizeT outSizeFull = 0xFFFFFFFF; /* 4GBytes limit */
+ SizeT outProcessed;
+ SizeT outSize;
+ SizeT outSizeHigh;
+ ELzmaStatus state;
+ SizeT compressedSize = (SizeT)(length - LZMA_PROPS_SIZE);
+
+ debug ("LZMA: Image address............... 0x%lx\n", inStream);
+ debug ("LZMA: Properties address.......... 0x%lx\n", inStream + LZMA_PROPERTIES_OFFSET);
+ debug ("LZMA: Uncompressed size address... 0x%lx\n", inStream + LZMA_SIZE_OFFSET);
+ debug ("LZMA: Compressed data address..... 0x%lx\n", inStream + LZMA_DATA_OFFSET);
+ debug ("LZMA: Destination address......... 0x%lx\n", outStream);
+
+ memset(&state, 0, sizeof(state));
+
+ outSize = 0;
+ outSizeHigh = 0;
+ /* Read the uncompressed size */
+ for (i = 0; i < 8; i++) {
+ unsigned char b = inStream[LZMA_SIZE_OFFSET + i];
+ if (i < 4) {
+ outSize += (UInt32)(b) << (i * 8);
+ } else {
+ outSizeHigh += (UInt32)(b) << ((i - 4) * 8);
+ }
+ }
+
+ outSizeFull = (SizeT)outSize;
+ if (sizeof(SizeT) >= 8) {
+ /*
+ * SizeT is a 64 bit uint => We can manage files larger than 4GB!
+ *
+ */
+ outSizeFull |= (((SizeT)outSizeHigh << 16) << 16);
+ } else if (outSizeHigh != 0 || (UInt32)(SizeT)outSize != outSize) {
+ /*
+ * SizeT is a 32 bit uint => We cannot manage files larger than
+ * 4GB! Assume however that all 0xf values is "unknown size" and
+ * not actually a file of 2^64 bits.
+ *
+ */
+ if (outSizeHigh != (SizeT)-1 || outSize != (SizeT)-1) {
+ debug ("LZMA: 64bit support not enabled.\n");
+ return SZ_ERROR_DATA;
+ }
+ }
+
+ debug ("LZMA: Uncompresed size............ 0x%lx\n", outSizeFull);
+ debug ("LZMA: Compresed size.............. 0x%lx\n", compressedSize);
+
+ g_Alloc.Alloc = SzAlloc;
+ g_Alloc.Free = SzFree;
+
+ /* Decompress */
+ outProcessed = outSizeFull;
+
+ WATCHDOG_RESET();
+
+ res = LzmaDecode(
+ outStream, &outProcessed,
+ inStream + LZMA_DATA_OFFSET, &compressedSize,
+ inStream, LZMA_PROPS_SIZE, LZMA_FINISH_ANY, &state, &g_Alloc);
+ *uncompressedSize = outProcessed;
+ if (res != SZ_OK) {
+ return res;
+ }
+
+ return res;
+}
+
+#endif
diff --git a/lib/lzma/LzmaTools.h b/lib/lzma/LzmaTools.h
new file mode 100644
index 00000000000..2db80fc0f47
--- /dev/null
+++ b/lib/lzma/LzmaTools.h
@@ -0,0 +1,35 @@
+/*
+ * Usefuls routines based on the LzmaTest.c file from LZMA SDK 4.65
+ *
+ * Copyright (C) 2007-2008 Industrie Dial Face S.p.A.
+ * Luigi 'Comio' Mantellini (luigi.mantellini@idf-hit.com)
+ *
+ * Copyright (C) 1999-2005 Igor Pavlov
+ *
+ * See file CREDITS for list of people who contributed to this
+ * project.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
+ * MA 02111-1307 USA
+ */
+
+#ifndef __LZMA_TOOL_H__
+#define __LZMA_TOOL_H__
+
+#include <lzma/LzmaTypes.h>
+
+extern int lzmaBuffToBuffDecompress (unsigned char *outStream, SizeT *uncompressedSize,
+ unsigned char *inStream, SizeT length);
+#endif
diff --git a/lib/lzma/Makefile b/lib/lzma/Makefile
new file mode 100644
index 00000000000..57f03b0cd78
--- /dev/null
+++ b/lib/lzma/Makefile
@@ -0,0 +1,51 @@
+#
+# Copyright (C) 2007-2008 Industrie Dial Face S.p.A.
+# Luigi 'Comio' Mantellini (luigi.mantellini@idf-hit.com)
+#
+# (C) Copyright 2003-2006
+# Wolfgang Denk, DENX Software Engineering, wd@denx.de.
+#
+# See file CREDITS for list of people who contributed to this
+# project.
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License as
+# published by the Free Software Foundation; either version 2 of
+# the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston,
+# MA 02111-1307 USA
+#
+
+include $(TOPDIR)/config.mk
+
+LIB = $(obj)liblzma.a
+
+SOBJS =
+
+CFLAGS += -D_LZMA_PROB32
+
+COBJS-$(CONFIG_LZMA) += LzmaDec.o LzmaTools.o
+
+COBJS = $(COBJS-y)
+SRCS := $(SOBJS:.o=.S) $(COBJS:.o=.c)
+OBJS := $(addprefix $(obj),$(SOBJS) $(COBJS))
+
+$(LIB): $(obj).depend $(OBJS)
+ $(AR) $(ARFLAGS) $@ $(OBJS)
+
+#########################################################################
+
+# defines $(obj).depend target
+include $(SRCTREE)/rules.mk
+
+sinclude $(obj).depend
+
+#########################################################################
diff --git a/lib/lzma/README.txt b/lib/lzma/README.txt
new file mode 100644
index 00000000000..23a9be28273
--- /dev/null
+++ b/lib/lzma/README.txt
@@ -0,0 +1,28 @@
+The lib_lzma functionality was written by Igor Pavlov.
+The original source cames from the LZMA SDK web page:
+
+URL: http://www.7-zip.org/sdk.html
+Author: Igor Pavlov
+
+The import is made using the import_lzmasdk.sh script that:
+
+* untars the lzmaXYY.tar.bz2 file (from the download web page)
+* copies the files LzmaDec.h, Types.h, LzmaDec.c, history.txt,
+ and lzma.txt from source archive into the lib_lzma directory (pwd).
+
+Example:
+
+ . import_lzmasdk.sh ~/lzma465.tar.bz2
+
+Notice: The files from lzma sdk are _not modified_ by this script!
+
+The files LzmaTools.{c,h} are provided to export the lzmaBuffToBuffDecompress()
+function that wraps the complex LzmaDecode() function from the LZMA SDK. The
+do_bootm() function uses the lzmaBuffToBuffDecopress() function to expand the
+compressed image.
+
+The directory U-BOOT/include/lzma contains stubs files that permit to use the
+library directly from U-BOOT code without touching the original LZMA SDK's
+files.
+
+Luigi 'Comio' Mantellini <luigi.mantellini@idf-hit.com>
diff --git a/lib/lzma/Types.h b/lib/lzma/Types.h
new file mode 100644
index 00000000000..1af5cfc4d86
--- /dev/null
+++ b/lib/lzma/Types.h
@@ -0,0 +1,208 @@
+/* Types.h -- Basic types
+2008-11-23 : Igor Pavlov : Public domain */
+
+#ifndef __7Z_TYPES_H
+#define __7Z_TYPES_H
+
+#include <stddef.h>
+
+#ifdef _WIN32
+#include <windows.h>
+#endif
+
+#define SZ_OK 0
+
+#define SZ_ERROR_DATA 1
+#define SZ_ERROR_MEM 2
+#define SZ_ERROR_CRC 3
+#define SZ_ERROR_UNSUPPORTED 4
+#define SZ_ERROR_PARAM 5
+#define SZ_ERROR_INPUT_EOF 6
+#define SZ_ERROR_OUTPUT_EOF 7
+#define SZ_ERROR_READ 8
+#define SZ_ERROR_WRITE 9
+#define SZ_ERROR_PROGRESS 10
+#define SZ_ERROR_FAIL 11
+#define SZ_ERROR_THREAD 12
+
+#define SZ_ERROR_ARCHIVE 16
+#define SZ_ERROR_NO_ARCHIVE 17
+
+typedef int SRes;
+
+#ifdef _WIN32
+typedef DWORD WRes;
+#else
+typedef int WRes;
+#endif
+
+#ifndef RINOK
+#define RINOK(x) { int __result__ = (x); if (__result__ != 0) return __result__; }
+#endif
+
+typedef unsigned char Byte;
+typedef short Int16;
+typedef unsigned short UInt16;
+
+#ifdef _LZMA_UINT32_IS_ULONG
+typedef long Int32;
+typedef unsigned long UInt32;
+#else
+typedef int Int32;
+typedef unsigned int UInt32;
+#endif
+
+#ifdef _SZ_NO_INT_64
+
+/* define _SZ_NO_INT_64, if your compiler doesn't support 64-bit integers.
+ NOTES: Some code will work incorrectly in that case! */
+
+typedef long Int64;
+typedef unsigned long UInt64;
+
+#else
+
+#if defined(_MSC_VER) || defined(__BORLANDC__)
+typedef __int64 Int64;
+typedef unsigned __int64 UInt64;
+#else
+typedef long long int Int64;
+typedef unsigned long long int UInt64;
+#endif
+
+#endif
+
+#ifdef _LZMA_NO_SYSTEM_SIZE_T
+typedef UInt32 SizeT;
+#else
+typedef size_t SizeT;
+#endif
+
+typedef int Bool;
+#define True 1
+#define False 0
+
+
+#ifdef _MSC_VER
+
+#if _MSC_VER >= 1300
+#define MY_NO_INLINE __declspec(noinline)
+#else
+#define MY_NO_INLINE
+#endif
+
+#define MY_CDECL __cdecl
+#define MY_STD_CALL __stdcall
+#define MY_FAST_CALL MY_NO_INLINE __fastcall
+
+#else
+
+#define MY_CDECL
+#define MY_STD_CALL
+#define MY_FAST_CALL
+
+#endif
+
+
+/* The following interfaces use first parameter as pointer to structure */
+
+typedef struct
+{
+ SRes (*Read)(void *p, void *buf, size_t *size);
+ /* if (input(*size) != 0 && output(*size) == 0) means end_of_stream.
+ (output(*size) < input(*size)) is allowed */
+} ISeqInStream;
+
+/* it can return SZ_ERROR_INPUT_EOF */
+SRes SeqInStream_Read(ISeqInStream *stream, void *buf, size_t size);
+SRes SeqInStream_Read2(ISeqInStream *stream, void *buf, size_t size, SRes errorType);
+SRes SeqInStream_ReadByte(ISeqInStream *stream, Byte *buf);
+
+typedef struct
+{
+ size_t (*Write)(void *p, const void *buf, size_t size);
+ /* Returns: result - the number of actually written bytes.
+ (result < size) means error */
+} ISeqOutStream;
+
+typedef enum
+{
+ SZ_SEEK_SET = 0,
+ SZ_SEEK_CUR = 1,
+ SZ_SEEK_END = 2
+} ESzSeek;
+
+typedef struct
+{
+ SRes (*Read)(void *p, void *buf, size_t *size); /* same as ISeqInStream::Read */
+ SRes (*Seek)(void *p, Int64 *pos, ESzSeek origin);
+} ISeekInStream;
+
+typedef struct
+{
+ SRes (*Look)(void *p, void **buf, size_t *size);
+ /* if (input(*size) != 0 && output(*size) == 0) means end_of_stream.
+ (output(*size) > input(*size)) is not allowed
+ (output(*size) < input(*size)) is allowed */
+ SRes (*Skip)(void *p, size_t offset);
+ /* offset must be <= output(*size) of Look */
+
+ SRes (*Read)(void *p, void *buf, size_t *size);
+ /* reads directly (without buffer). It's same as ISeqInStream::Read */
+ SRes (*Seek)(void *p, Int64 *pos, ESzSeek origin);
+} ILookInStream;
+
+SRes LookInStream_LookRead(ILookInStream *stream, void *buf, size_t *size);
+SRes LookInStream_SeekTo(ILookInStream *stream, UInt64 offset);
+
+/* reads via ILookInStream::Read */
+SRes LookInStream_Read2(ILookInStream *stream, void *buf, size_t size, SRes errorType);
+SRes LookInStream_Read(ILookInStream *stream, void *buf, size_t size);
+
+#define LookToRead_BUF_SIZE (1 << 14)
+
+typedef struct
+{
+ ILookInStream s;
+ ISeekInStream *realStream;
+ size_t pos;
+ size_t size;
+ Byte buf[LookToRead_BUF_SIZE];
+} CLookToRead;
+
+void LookToRead_CreateVTable(CLookToRead *p, int lookahead);
+void LookToRead_Init(CLookToRead *p);
+
+typedef struct
+{
+ ISeqInStream s;
+ ILookInStream *realStream;
+} CSecToLook;
+
+void SecToLook_CreateVTable(CSecToLook *p);
+
+typedef struct
+{
+ ISeqInStream s;
+ ILookInStream *realStream;
+} CSecToRead;
+
+void SecToRead_CreateVTable(CSecToRead *p);
+
+typedef struct
+{
+ SRes (*Progress)(void *p, UInt64 inSize, UInt64 outSize);
+ /* Returns: result. (result != SZ_OK) means break.
+ Value (UInt64)(Int64)-1 for size means unknown value. */
+} ICompressProgress;
+
+typedef struct
+{
+ void *(*Alloc)(void *p, size_t size);
+ void (*Free)(void *p, void *address); /* address can be 0 */
+} ISzAlloc;
+
+#define IAlloc_Alloc(p, size) (p)->Alloc((p), size)
+#define IAlloc_Free(p, a) (p)->Free((p), a)
+
+#endif
diff --git a/lib/lzma/history.txt b/lib/lzma/history.txt
new file mode 100644
index 00000000000..624fb1d4b1d
--- /dev/null
+++ b/lib/lzma/history.txt
@@ -0,0 +1,236 @@
+HISTORY of the LZMA SDK
+-----------------------
+
+4.65 2009-02-03
+-------------------------
+- Some minor fixes
+
+
+4.63 2008-12-31
+-------------------------
+- Some minor fixes
+
+
+4.61 beta 2008-11-23
+-------------------------
+- The bug in ANSI-C LZMA Decoder was fixed:
+ If encoded stream was corrupted, decoder could access memory
+ outside of allocated range.
+- Some changes in ANSI-C 7z Decoder interfaces.
+- LZMA SDK is placed in the public domain.
+
+
+4.60 beta 2008-08-19
+-------------------------
+- Some minor fixes.
+
+
+4.59 beta 2008-08-13
+-------------------------
+- The bug was fixed:
+ LZMA Encoder in fast compression mode could access memory outside of
+ allocated range in some rare cases.
+
+
+4.58 beta 2008-05-05
+-------------------------
+- ANSI-C LZMA Decoder was rewritten for speed optimizations.
+- ANSI-C LZMA Encoder was included to LZMA SDK.
+- C++ LZMA code now is just wrapper over ANSI-C code.
+
+
+4.57 2007-12-12
+-------------------------
+- Speed optimizations in Ñ++ LZMA Decoder.
+- Small changes for more compatibility with some C/C++ compilers.
+
+
+4.49 beta 2007-07-05
+-------------------------
+- .7z ANSI-C Decoder:
+ - now it supports BCJ and BCJ2 filters
+ - now it supports files larger than 4 GB.
+ - now it supports "Last Write Time" field for files.
+- C++ code for .7z archives compressing/decompressing from 7-zip
+ was included to LZMA SDK.
+
+
+4.43 2006-06-04
+-------------------------
+- Small changes for more compatibility with some C/C++ compilers.
+
+
+4.42 2006-05-15
+-------------------------
+- Small changes in .h files in ANSI-C version.
+
+
+4.39 beta 2006-04-14
+-------------------------
+- The bug in versions 4.33b:4.38b was fixed:
+ C++ version of LZMA encoder could not correctly compress
+ files larger than 2 GB with HC4 match finder (-mfhc4).
+
+
+4.37 beta 2005-04-06
+-------------------------
+- Fixes in C++ code: code could no be compiled if _NO_EXCEPTIONS was defined.
+
+
+4.35 beta 2005-03-02
+-------------------------
+- The bug was fixed in C++ version of LZMA Decoder:
+ If encoded stream was corrupted, decoder could access memory
+ outside of allocated range.
+
+
+4.34 beta 2006-02-27
+-------------------------
+- Compressing speed and memory requirements for compressing were increased
+- LZMA now can use only these match finders: HC4, BT2, BT3, BT4
+
+
+4.32 2005-12-09
+-------------------------
+- Java version of LZMA SDK was included
+
+
+4.30 2005-11-20
+-------------------------
+- Compression ratio was improved in -a2 mode
+- Speed optimizations for compressing in -a2 mode
+- -fb switch now supports values up to 273
+- The bug in 7z_C (7zIn.c) was fixed:
+ It used Alloc/Free functions from different memory pools.
+ So if program used two memory pools, it worked incorrectly.
+- 7z_C: .7z format supporting was improved
+- LZMA# SDK (C#.NET version) was included
+
+
+4.27 (Updated) 2005-09-21
+-------------------------
+- Some GUIDs/interfaces in C++ were changed.
+ IStream.h:
+ ISequentialInStream::Read now works as old ReadPart
+ ISequentialOutStream::Write now works as old WritePart
+
+
+4.27 2005-08-07
+-------------------------
+- The bug in LzmaDecodeSize.c was fixed:
+ if _LZMA_IN_CB and _LZMA_OUT_READ were defined,
+ decompressing worked incorrectly.
+
+
+4.26 2005-08-05
+-------------------------
+- Fixes in 7z_C code and LzmaTest.c:
+ previous versions could work incorrectly,
+ if malloc(0) returns 0
+
+
+4.23 2005-06-29
+-------------------------
+- Small fixes in C++ code
+
+
+4.22 2005-06-10
+-------------------------
+- Small fixes
+
+
+4.21 2005-06-08
+-------------------------
+- Interfaces for ANSI-C LZMA Decoder (LzmaDecode.c) were changed
+- New additional version of ANSI-C LZMA Decoder with zlib-like interface:
+ - LzmaStateDecode.h
+ - LzmaStateDecode.c
+ - LzmaStateTest.c
+- ANSI-C LZMA Decoder now can decompress files larger than 4 GB
+
+
+4.17 2005-04-18
+-------------------------
+- New example for RAM->RAM compressing/decompressing:
+ LZMA + BCJ (filter for x86 code):
+ - LzmaRam.h
+ - LzmaRam.cpp
+ - LzmaRamDecode.h
+ - LzmaRamDecode.c
+ - -f86 switch for lzma.exe
+
+
+4.16 2005-03-29
+-------------------------
+- The bug was fixed in LzmaDecode.c (ANSI-C LZMA Decoder):
+ If _LZMA_OUT_READ was defined, and if encoded stream was corrupted,
+ decoder could access memory outside of allocated range.
+- Speed optimization of ANSI-C LZMA Decoder (now it's about 20% faster).
+ Old version of LZMA Decoder now is in file LzmaDecodeSize.c.
+ LzmaDecodeSize.c can provide slightly smaller code than LzmaDecode.c
+- Small speed optimization in LZMA C++ code
+- filter for SPARC's code was added
+- Simplified version of .7z ANSI-C Decoder was included
+
+
+4.06 2004-09-05
+-------------------------
+- The bug in v4.05 was fixed:
+ LZMA-Encoder didn't release output stream in some cases.
+
+
+4.05 2004-08-25
+-------------------------
+- Source code of filters for x86, IA-64, ARM, ARM-Thumb
+ and PowerPC code was included to SDK
+- Some internal minor changes
+
+
+4.04 2004-07-28
+-------------------------
+- More compatibility with some C++ compilers
+
+
+4.03 2004-06-18
+-------------------------
+- "Benchmark" command was added. It measures compressing
+ and decompressing speed and shows rating values.
+ Also it checks hardware errors.
+
+
+4.02 2004-06-10
+-------------------------
+- C++ LZMA Encoder/Decoder code now is more portable
+ and it can be compiled by GCC on Linux.
+
+
+4.01 2004-02-15
+-------------------------
+- Some detection of data corruption was enabled.
+ LzmaDecode.c / RangeDecoderReadByte
+ .....
+ {
+ rd->ExtraBytes = 1;
+ return 0xFF;
+ }
+
+
+4.00 2004-02-13
+-------------------------
+- Original version of LZMA SDK
+
+
+
+HISTORY of the LZMA
+-------------------
+ 2001-2008: Improvements to LZMA compressing/decompressing code,
+ keeping compatibility with original LZMA format
+ 1996-2001: Development of LZMA compression format
+
+ Some milestones:
+
+ 2001-08-30: LZMA compression was added to 7-Zip
+ 1999-01-02: First version of 7-Zip was released
+
+
+End of document
diff --git a/lib/lzma/import_lzmasdk.sh b/lib/lzma/import_lzmasdk.sh
new file mode 100644
index 00000000000..1e0f6863aab
--- /dev/null
+++ b/lib/lzma/import_lzmasdk.sh
@@ -0,0 +1,36 @@
+#!/bin/sh
+
+usage() {
+ echo "Usage: $0 lzmaVERSION.tar.bz2" >&2
+ echo >&2
+ exit 1
+}
+
+if [ "$1" = "" ] ; then
+ usage
+fi
+
+if [ ! -f $1 ] ; then
+ echo "$1 doesn't exist!" >&2
+ exit 1
+fi
+
+BASENAME=`basename $1 .tar.bz2`
+TMPDIR=/tmp/tmp_lib_$BASENAME
+FILES="C/LzmaDec.h
+ C/Types.h
+ C/LzmaDec.c
+ history.txt
+ lzma.txt"
+
+mkdir -p $TMPDIR
+echo "Untar $1 -> $TMPDIR"
+tar -jxf $1 -C $TMPDIR
+
+for i in $FILES; do
+ echo Copying $TMPDIR/$i \-\> `basename $i`
+ cp $TMPDIR/$i .
+ chmod -x `basename $i`
+done
+
+echo "done!"
diff --git a/lib/lzma/license.txt b/lib/lzma/license.txt
new file mode 100644
index 00000000000..48b9820c408
--- /dev/null
+++ b/lib/lzma/license.txt
@@ -0,0 +1,3 @@
+ License
+
+LZMA SDK is placed in the public domain.
diff --git a/lib/lzma/lzma.txt b/lib/lzma/lzma.txt
new file mode 100644
index 00000000000..aa20f9dc5ce
--- /dev/null
+++ b/lib/lzma/lzma.txt
@@ -0,0 +1,594 @@
+LZMA SDK 4.65
+-------------
+
+LZMA SDK provides the documentation, samples, header files, libraries,
+and tools you need to develop applications that use LZMA compression.
+
+LZMA is default and general compression method of 7z format
+in 7-Zip compression program (www.7-zip.org). LZMA provides high
+compression ratio and very fast decompression.
+
+LZMA is an improved version of famous LZ77 compression algorithm.
+It was improved in way of maximum increasing of compression ratio,
+keeping high decompression speed and low memory requirements for
+decompressing.
+
+
+
+LICENSE
+-------
+
+LZMA SDK is written and placed in the public domain by Igor Pavlov.
+
+
+LZMA SDK Contents
+-----------------
+
+LZMA SDK includes:
+
+ - ANSI-C/C++/C#/Java source code for LZMA compressing and decompressing
+ - Compiled file->file LZMA compressing/decompressing program for Windows system
+
+
+UNIX/Linux version
+------------------
+To compile C++ version of file->file LZMA encoding, go to directory
+C++/7zip/Compress/LZMA_Alone
+and call make to recompile it:
+ make -f makefile.gcc clean all
+
+In some UNIX/Linux versions you must compile LZMA with static libraries.
+To compile with static libraries, you can use
+LIB = -lm -static
+
+
+Files
+---------------------
+lzma.txt - LZMA SDK description (this file)
+7zFormat.txt - 7z Format description
+7zC.txt - 7z ANSI-C Decoder description
+methods.txt - Compression method IDs for .7z
+lzma.exe - Compiled file->file LZMA encoder/decoder for Windows
+history.txt - history of the LZMA SDK
+
+
+Source code structure
+---------------------
+
+C/ - C files
+ 7zCrc*.* - CRC code
+ Alloc.* - Memory allocation functions
+ Bra*.* - Filters for x86, IA-64, ARM, ARM-Thumb, PowerPC and SPARC code
+ LzFind.* - Match finder for LZ (LZMA) encoders
+ LzFindMt.* - Match finder for LZ (LZMA) encoders for multithreading encoding
+ LzHash.h - Additional file for LZ match finder
+ LzmaDec.* - LZMA decoding
+ LzmaEnc.* - LZMA encoding
+ LzmaLib.* - LZMA Library for DLL calling
+ Types.h - Basic types for another .c files
+ Threads.* - The code for multithreading.
+
+ LzmaLib - LZMA Library (.DLL for Windows)
+
+ LzmaUtil - LZMA Utility (file->file LZMA encoder/decoder).
+
+ Archive - files related to archiving
+ 7z - 7z ANSI-C Decoder
+
+CPP/ -- CPP files
+
+ Common - common files for C++ projects
+ Windows - common files for Windows related code
+
+ 7zip - files related to 7-Zip Project
+
+ Common - common files for 7-Zip
+
+ Compress - files related to compression/decompression
+
+ Copy - Copy coder
+ RangeCoder - Range Coder (special code of compression/decompression)
+ LZMA - LZMA compression/decompression on C++
+ LZMA_Alone - file->file LZMA compression/decompression
+ Branch - Filters for x86, IA-64, ARM, ARM-Thumb, PowerPC and SPARC code
+
+ Archive - files related to archiving
+
+ Common - common files for archive handling
+ 7z - 7z C++ Encoder/Decoder
+
+ Bundles - Modules that are bundles of other modules
+
+ Alone7z - 7zr.exe: Standalone version of 7z.exe that supports only 7z/LZMA/BCJ/BCJ2
+ Format7zR - 7zr.dll: Reduced version of 7za.dll: extracting/compressing to 7z/LZMA/BCJ/BCJ2
+ Format7zExtractR - 7zxr.dll: Reduced version of 7zxa.dll: extracting from 7z/LZMA/BCJ/BCJ2.
+
+ UI - User Interface files
+
+ Client7z - Test application for 7za.dll, 7zr.dll, 7zxr.dll
+ Common - Common UI files
+ Console - Code for console archiver
+
+
+
+CS/ - C# files
+ 7zip
+ Common - some common files for 7-Zip
+ Compress - files related to compression/decompression
+ LZ - files related to LZ (Lempel-Ziv) compression algorithm
+ LZMA - LZMA compression/decompression
+ LzmaAlone - file->file LZMA compression/decompression
+ RangeCoder - Range Coder (special code of compression/decompression)
+
+Java/ - Java files
+ SevenZip
+ Compression - files related to compression/decompression
+ LZ - files related to LZ (Lempel-Ziv) compression algorithm
+ LZMA - LZMA compression/decompression
+ RangeCoder - Range Coder (special code of compression/decompression)
+
+
+C/C++ source code of LZMA SDK is part of 7-Zip project.
+7-Zip source code can be downloaded from 7-Zip's SourceForge page:
+
+ http://sourceforge.net/projects/sevenzip/
+
+
+
+LZMA features
+-------------
+ - Variable dictionary size (up to 1 GB)
+ - Estimated compressing speed: about 2 MB/s on 2 GHz CPU
+ - Estimated decompressing speed:
+ - 20-30 MB/s on 2 GHz Core 2 or AMD Athlon 64
+ - 1-2 MB/s on 200 MHz ARM, MIPS, PowerPC or other simple RISC
+ - Small memory requirements for decompressing (16 KB + DictionarySize)
+ - Small code size for decompressing: 5-8 KB
+
+LZMA decoder uses only integer operations and can be
+implemented in any modern 32-bit CPU (or on 16-bit CPU with some conditions).
+
+Some critical operations that affect the speed of LZMA decompression:
+ 1) 32*16 bit integer multiply
+ 2) Misspredicted branches (penalty mostly depends from pipeline length)
+ 3) 32-bit shift and arithmetic operations
+
+The speed of LZMA decompressing mostly depends from CPU speed.
+Memory speed has no big meaning. But if your CPU has small data cache,
+overall weight of memory speed will slightly increase.
+
+
+How To Use
+----------
+
+Using LZMA encoder/decoder executable
+--------------------------------------
+
+Usage: LZMA <e|d> inputFile outputFile [<switches>...]
+
+ e: encode file
+
+ d: decode file
+
+ b: Benchmark. There are two tests: compressing and decompressing
+ with LZMA method. Benchmark shows rating in MIPS (million
+ instructions per second). Rating value is calculated from
+ measured speed and it is normalized with Intel's Core 2 results.
+ Also Benchmark checks possible hardware errors (RAM
+ errors in most cases). Benchmark uses these settings:
+ (-a1, -d21, -fb32, -mfbt4). You can change only -d parameter.
+ Also you can change the number of iterations. Example for 30 iterations:
+ LZMA b 30
+ Default number of iterations is 10.
+
+<Switches>
+
+
+ -a{N}: set compression mode 0 = fast, 1 = normal
+ default: 1 (normal)
+
+ d{N}: Sets Dictionary size - [0, 30], default: 23 (8MB)
+ The maximum value for dictionary size is 1 GB = 2^30 bytes.
+ Dictionary size is calculated as DictionarySize = 2^N bytes.
+ For decompressing file compressed by LZMA method with dictionary
+ size D = 2^N you need about D bytes of memory (RAM).
+
+ -fb{N}: set number of fast bytes - [5, 273], default: 128
+ Usually big number gives a little bit better compression ratio
+ and slower compression process.
+
+ -lc{N}: set number of literal context bits - [0, 8], default: 3
+ Sometimes lc=4 gives gain for big files.
+
+ -lp{N}: set number of literal pos bits - [0, 4], default: 0
+ lp switch is intended for periodical data when period is
+ equal 2^N. For example, for 32-bit (4 bytes)
+ periodical data you can use lp=2. Often it's better to set lc0,
+ if you change lp switch.
+
+ -pb{N}: set number of pos bits - [0, 4], default: 2
+ pb switch is intended for periodical data
+ when period is equal 2^N.
+
+ -mf{MF_ID}: set Match Finder. Default: bt4.
+ Algorithms from hc* group doesn't provide good compression
+ ratio, but they often works pretty fast in combination with
+ fast mode (-a0).
+
+ Memory requirements depend from dictionary size
+ (parameter "d" in table below).
+
+ MF_ID Memory Description
+
+ bt2 d * 9.5 + 4MB Binary Tree with 2 bytes hashing.
+ bt3 d * 11.5 + 4MB Binary Tree with 3 bytes hashing.
+ bt4 d * 11.5 + 4MB Binary Tree with 4 bytes hashing.
+ hc4 d * 7.5 + 4MB Hash Chain with 4 bytes hashing.
+
+ -eos: write End Of Stream marker. By default LZMA doesn't write
+ eos marker, since LZMA decoder knows uncompressed size
+ stored in .lzma file header.
+
+ -si: Read data from stdin (it will write End Of Stream marker).
+ -so: Write data to stdout
+
+
+Examples:
+
+1) LZMA e file.bin file.lzma -d16 -lc0
+
+compresses file.bin to file.lzma with 64 KB dictionary (2^16=64K)
+and 0 literal context bits. -lc0 allows to reduce memory requirements
+for decompression.
+
+
+2) LZMA e file.bin file.lzma -lc0 -lp2
+
+compresses file.bin to file.lzma with settings suitable
+for 32-bit periodical data (for example, ARM or MIPS code).
+
+3) LZMA d file.lzma file.bin
+
+decompresses file.lzma to file.bin.
+
+
+Compression ratio hints
+-----------------------
+
+Recommendations
+---------------
+
+To increase the compression ratio for LZMA compressing it's desirable
+to have aligned data (if it's possible) and also it's desirable to locate
+data in such order, where code is grouped in one place and data is
+grouped in other place (it's better than such mixing: code, data, code,
+data, ...).
+
+
+Filters
+-------
+You can increase the compression ratio for some data types, using
+special filters before compressing. For example, it's possible to
+increase the compression ratio on 5-10% for code for those CPU ISAs:
+x86, IA-64, ARM, ARM-Thumb, PowerPC, SPARC.
+
+You can find C source code of such filters in C/Bra*.* files
+
+You can check the compression ratio gain of these filters with such
+7-Zip commands (example for ARM code):
+No filter:
+ 7z a a1.7z a.bin -m0=lzma
+
+With filter for little-endian ARM code:
+ 7z a a2.7z a.bin -m0=arm -m1=lzma
+
+It works in such manner:
+Compressing = Filter_encoding + LZMA_encoding
+Decompressing = LZMA_decoding + Filter_decoding
+
+Compressing and decompressing speed of such filters is very high,
+so it will not increase decompressing time too much.
+Moreover, it reduces decompression time for LZMA_decoding,
+since compression ratio with filtering is higher.
+
+These filters convert CALL (calling procedure) instructions
+from relative offsets to absolute addresses, so such data becomes more
+compressible.
+
+For some ISAs (for example, for MIPS) it's impossible to get gain from such filter.
+
+
+LZMA compressed file format
+---------------------------
+Offset Size Description
+ 0 1 Special LZMA properties (lc,lp, pb in encoded form)
+ 1 4 Dictionary size (little endian)
+ 5 8 Uncompressed size (little endian). -1 means unknown size
+ 13 Compressed data
+
+
+ANSI-C LZMA Decoder
+~~~~~~~~~~~~~~~~~~~
+
+Please note that interfaces for ANSI-C code were changed in LZMA SDK 4.58.
+If you want to use old interfaces you can download previous version of LZMA SDK
+from sourceforge.net site.
+
+To use ANSI-C LZMA Decoder you need the following files:
+1) LzmaDec.h + LzmaDec.c + Types.h
+LzmaUtil/LzmaUtil.c is example application that uses these files.
+
+
+Memory requirements for LZMA decoding
+-------------------------------------
+
+Stack usage of LZMA decoding function for local variables is not
+larger than 200-400 bytes.
+
+LZMA Decoder uses dictionary buffer and internal state structure.
+Internal state structure consumes
+ state_size = (4 + (1.5 << (lc + lp))) KB
+by default (lc=3, lp=0), state_size = 16 KB.
+
+
+How To decompress data
+----------------------
+
+LZMA Decoder (ANSI-C version) now supports 2 interfaces:
+1) Single-call Decompressing
+2) Multi-call State Decompressing (zlib-like interface)
+
+You must use external allocator:
+Example:
+void *SzAlloc(void *p, size_t size) { p = p; return malloc(size); }
+void SzFree(void *p, void *address) { p = p; free(address); }
+ISzAlloc alloc = { SzAlloc, SzFree };
+
+You can use p = p; operator to disable compiler warnings.
+
+
+Single-call Decompressing
+-------------------------
+When to use: RAM->RAM decompressing
+Compile files: LzmaDec.h + LzmaDec.c + Types.h
+Compile defines: no defines
+Memory Requirements:
+ - Input buffer: compressed size
+ - Output buffer: uncompressed size
+ - LZMA Internal Structures: state_size (16 KB for default settings)
+
+Interface:
+ int LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
+ const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
+ ELzmaStatus *status, ISzAlloc *alloc);
+ In:
+ dest - output data
+ destLen - output data size
+ src - input data
+ srcLen - input data size
+ propData - LZMA properties (5 bytes)
+ propSize - size of propData buffer (5 bytes)
+ finishMode - It has meaning only if the decoding reaches output limit (*destLen).
+ LZMA_FINISH_ANY - Decode just destLen bytes.
+ LZMA_FINISH_END - Stream must be finished after (*destLen).
+ You can use LZMA_FINISH_END, when you know that
+ current output buffer covers last bytes of stream.
+ alloc - Memory allocator.
+
+ Out:
+ destLen - processed output size
+ srcLen - processed input size
+
+ Output:
+ SZ_OK
+ status:
+ LZMA_STATUS_FINISHED_WITH_MARK
+ LZMA_STATUS_NOT_FINISHED
+ LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK
+ SZ_ERROR_DATA - Data error
+ SZ_ERROR_MEM - Memory allocation error
+ SZ_ERROR_UNSUPPORTED - Unsupported properties
+ SZ_ERROR_INPUT_EOF - It needs more bytes in input buffer (src).
+
+ If LZMA decoder sees end_marker before reaching output limit, it returns OK result,
+ and output value of destLen will be less than output buffer size limit.
+
+ You can use multiple checks to test data integrity after full decompression:
+ 1) Check Result and "status" variable.
+ 2) Check that output(destLen) = uncompressedSize, if you know real uncompressedSize.
+ 3) Check that output(srcLen) = compressedSize, if you know real compressedSize.
+ You must use correct finish mode in that case. */
+
+
+Multi-call State Decompressing (zlib-like interface)
+----------------------------------------------------
+
+When to use: file->file decompressing
+Compile files: LzmaDec.h + LzmaDec.c + Types.h
+
+Memory Requirements:
+ - Buffer for input stream: any size (for example, 16 KB)
+ - Buffer for output stream: any size (for example, 16 KB)
+ - LZMA Internal Structures: state_size (16 KB for default settings)
+ - LZMA dictionary (dictionary size is encoded in LZMA properties header)
+
+1) read LZMA properties (5 bytes) and uncompressed size (8 bytes, little-endian) to header:
+ unsigned char header[LZMA_PROPS_SIZE + 8];
+ ReadFile(inFile, header, sizeof(header)
+
+2) Allocate CLzmaDec structures (state + dictionary) using LZMA properties
+
+ CLzmaDec state;
+ LzmaDec_Constr(&state);
+ res = LzmaDec_Allocate(&state, header, LZMA_PROPS_SIZE, &g_Alloc);
+ if (res != SZ_OK)
+ return res;
+
+3) Init LzmaDec structure before any new LZMA stream. And call LzmaDec_DecodeToBuf in loop
+
+ LzmaDec_Init(&state);
+ for (;;)
+ {
+ ...
+ int res = LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen,
+ const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode);
+ ...
+ }
+
+
+4) Free all allocated structures
+ LzmaDec_Free(&state, &g_Alloc);
+
+For full code example, look at C/LzmaUtil/LzmaUtil.c code.
+
+
+How To compress data
+--------------------
+
+Compile files: LzmaEnc.h + LzmaEnc.c + Types.h +
+LzFind.c + LzFind.h + LzFindMt.c + LzFindMt.h + LzHash.h
+
+Memory Requirements:
+ - (dictSize * 11.5 + 6 MB) + state_size
+
+Lzma Encoder can use two memory allocators:
+1) alloc - for small arrays.
+2) allocBig - for big arrays.
+
+For example, you can use Large RAM Pages (2 MB) in allocBig allocator for
+better compression speed. Note that Windows has bad implementation for
+Large RAM Pages.
+It's OK to use same allocator for alloc and allocBig.
+
+
+Single-call Compression with callbacks
+--------------------------------------
+
+Check C/LzmaUtil/LzmaUtil.c as example,
+
+When to use: file->file decompressing
+
+1) you must implement callback structures for interfaces:
+ISeqInStream
+ISeqOutStream
+ICompressProgress
+ISzAlloc
+
+static void *SzAlloc(void *p, size_t size) { p = p; return MyAlloc(size); }
+static void SzFree(void *p, void *address) { p = p; MyFree(address); }
+static ISzAlloc g_Alloc = { SzAlloc, SzFree };
+
+ CFileSeqInStream inStream;
+ CFileSeqOutStream outStream;
+
+ inStream.funcTable.Read = MyRead;
+ inStream.file = inFile;
+ outStream.funcTable.Write = MyWrite;
+ outStream.file = outFile;
+
+
+2) Create CLzmaEncHandle object;
+
+ CLzmaEncHandle enc;
+
+ enc = LzmaEnc_Create(&g_Alloc);
+ if (enc == 0)
+ return SZ_ERROR_MEM;
+
+
+3) initialize CLzmaEncProps properties;
+
+ LzmaEncProps_Init(&props);
+
+ Then you can change some properties in that structure.
+
+4) Send LZMA properties to LZMA Encoder
+
+ res = LzmaEnc_SetProps(enc, &props);
+
+5) Write encoded properties to header
+
+ Byte header[LZMA_PROPS_SIZE + 8];
+ size_t headerSize = LZMA_PROPS_SIZE;
+ UInt64 fileSize;
+ int i;
+
+ res = LzmaEnc_WriteProperties(enc, header, &headerSize);
+ fileSize = MyGetFileLength(inFile);
+ for (i = 0; i < 8; i++)
+ header[headerSize++] = (Byte)(fileSize >> (8 * i));
+ MyWriteFileAndCheck(outFile, header, headerSize)
+
+6) Call encoding function:
+ res = LzmaEnc_Encode(enc, &outStream.funcTable, &inStream.funcTable,
+ NULL, &g_Alloc, &g_Alloc);
+
+7) Destroy LZMA Encoder Object
+ LzmaEnc_Destroy(enc, &g_Alloc, &g_Alloc);
+
+
+If callback function return some error code, LzmaEnc_Encode also returns that code.
+
+
+Single-call RAM->RAM Compression
+--------------------------------
+
+Single-call RAM->RAM Compression is similar to Compression with callbacks,
+but you provide pointers to buffers instead of pointers to stream callbacks:
+
+HRes LzmaEncode(Byte *dest, SizeT *destLen, const Byte *src, SizeT srcLen,
+ CLzmaEncProps *props, Byte *propsEncoded, SizeT *propsSize, int writeEndMark,
+ ICompressProgress *progress, ISzAlloc *alloc, ISzAlloc *allocBig);
+
+Return code:
+ SZ_OK - OK
+ SZ_ERROR_MEM - Memory allocation error
+ SZ_ERROR_PARAM - Incorrect paramater
+ SZ_ERROR_OUTPUT_EOF - output buffer overflow
+ SZ_ERROR_THREAD - errors in multithreading functions (only for Mt version)
+
+
+
+LZMA Defines
+------------
+
+_LZMA_SIZE_OPT - Enable some optimizations in LZMA Decoder to get smaller executable code.
+
+_LZMA_PROB32 - It can increase the speed on some 32-bit CPUs, but memory usage for
+ some structures will be doubled in that case.
+
+_LZMA_UINT32_IS_ULONG - Define it if int is 16-bit on your compiler and long is 32-bit.
+
+_LZMA_NO_SYSTEM_SIZE_T - Define it if you don't want to use size_t type.
+
+
+C++ LZMA Encoder/Decoder
+~~~~~~~~~~~~~~~~~~~~~~~~
+C++ LZMA code use COM-like interfaces. So if you want to use it,
+you can study basics of COM/OLE.
+C++ LZMA code is just wrapper over ANSI-C code.
+
+
+C++ Notes
+~~~~~~~~~~~~~~~~~~~~~~~~
+If you use some C++ code folders in 7-Zip (for example, C++ code for .7z handling),
+you must check that you correctly work with "new" operator.
+7-Zip can be compiled with MSVC 6.0 that doesn't throw "exception" from "new" operator.
+So 7-Zip uses "CPP\Common\NewHandler.cpp" that redefines "new" operator:
+operator new(size_t size)
+{
+ void *p = ::malloc(size);
+ if (p == 0)
+ throw CNewException();
+ return p;
+}
+If you use MSCV that throws exception for "new" operator, you can compile without
+"NewHandler.cpp". So standard exception will be used. Actually some code of
+7-Zip catches any exception in internal code and converts it to HRESULT code.
+So you don't need to catch CNewException, if you call COM interfaces of 7-Zip.
+
+---
+
+http://www.7-zip.org
+http://www.7-zip.org/sdk.html
+http://www.7-zip.org/support.html