From 71478fd62d8483483abb34609cdabb7f9cbadfd6 Mon Sep 17 00:00:00 2001 From: root Date: Sat, 19 Dec 2015 14:18:43 +0000 Subject: Add hostTools from https://github.com/Noltari/cfe_bcm63xx --- hostTools/lzma/compress/7z.h | 12 + hostTools/lzma/compress/7zapi.cpp | 19 + hostTools/lzma/compress/7zapi.h | 16 + hostTools/lzma/compress/7zlzma.cpp | 79 +++ hostTools/lzma/compress/AriBitCoder.cpp | 21 + hostTools/lzma/compress/AriBitCoder.h | 101 +++ hostTools/lzma/compress/AriConst.h | 17 + hostTools/lzma/compress/AriPrice.h | 12 + hostTools/lzma/compress/BinTree.h | 64 ++ hostTools/lzma/compress/BinTree2.h | 13 + hostTools/lzma/compress/BinTree2Main.h | 13 + hostTools/lzma/compress/BinTree3.h | 17 + hostTools/lzma/compress/BinTree3Main.h | 17 + hostTools/lzma/compress/BinTree3Z.h | 14 + hostTools/lzma/compress/BinTree3ZMain.h | 14 + hostTools/lzma/compress/BinTree4.h | 19 + hostTools/lzma/compress/BinTree4Main.h | 19 + hostTools/lzma/compress/BinTree4b.h | 21 + hostTools/lzma/compress/BinTree4bMain.h | 21 + hostTools/lzma/compress/BinTreeMF.h | 19 + hostTools/lzma/compress/BinTreeMFMain.h | 30 + hostTools/lzma/compress/BinTreeMain.h | 502 +++++++++++++++ hostTools/lzma/compress/BitTreeCoder.h | 290 +++++++++ hostTools/lzma/compress/CRC.h | 27 + hostTools/lzma/compress/Const.h | 92 +++ hostTools/lzma/compress/IInOutStreams.cpp | 25 + hostTools/lzma/compress/IInOutStreams.h | 31 + hostTools/lzma/compress/InByte.cpp | 41 ++ hostTools/lzma/compress/InByte.h | 58 ++ hostTools/lzma/compress/LZMA.cpp | 23 + hostTools/lzma/compress/LZMA.h | 105 ++++ hostTools/lzma/compress/LZMADecoder.cpp | 276 +++++++++ hostTools/lzma/compress/LZMADecoder.h | 64 ++ hostTools/lzma/compress/LZMAEncoder.cpp | 981 ++++++++++++++++++++++++++++++ hostTools/lzma/compress/LZMAEncoder.h | 228 +++++++ hostTools/lzma/compress/LenCoder.cpp | 73 +++ hostTools/lzma/compress/LenCoder.h | 122 ++++ hostTools/lzma/compress/LiteralCoder.cpp | 66 ++ hostTools/lzma/compress/LiteralCoder.h | 160 +++++ hostTools/lzma/compress/OutByte.cpp | 45 ++ hostTools/lzma/compress/OutByte.h | 42 ++ hostTools/lzma/compress/Portable.h | 48 ++ hostTools/lzma/compress/RCDefs.h | 42 ++ hostTools/lzma/compress/RangeCoder.h | 232 +++++++ hostTools/lzma/compress/StdAfx.cpp | 8 + hostTools/lzma/compress/StdAfx.h | 22 + hostTools/lzma/compress/WindowIn.cpp | 97 +++ hostTools/lzma/compress/WindowIn.h | 91 +++ hostTools/lzma/compress/WindowOut.cpp | 71 +++ hostTools/lzma/compress/WindowOut.h | 71 +++ hostTools/lzma/compress/lzDecomp.cpp | 45 ++ hostTools/lzma/decompress/7z.h | 16 + hostTools/lzma/decompress/7zlzma.c | 57 ++ hostTools/lzma/decompress/AriBitCoder.h | 51 ++ hostTools/lzma/decompress/BitTreeCoder.h | 160 +++++ hostTools/lzma/decompress/IInOutStreams.c | 38 ++ hostTools/lzma/decompress/IInOutStreams.h | 62 ++ hostTools/lzma/decompress/LZMA.h | 83 +++ hostTools/lzma/decompress/LZMADecoder.c | 398 ++++++++++++ hostTools/lzma/decompress/LZMADecoder.h | 60 ++ hostTools/lzma/decompress/LenCoder.h | 75 +++ hostTools/lzma/decompress/LiteralCoder.h | 146 +++++ hostTools/lzma/decompress/Makefile | 6 + hostTools/lzma/decompress/Portable.h | 59 ++ hostTools/lzma/decompress/RCDefs.h | 43 ++ hostTools/lzma/decompress/RangeCoder.h | 56 ++ hostTools/lzma/decompress/WindowOut.h | 47 ++ hostTools/lzma/decompress/vxTypesOld.h | 289 +++++++++ 68 files changed, 6182 insertions(+) create mode 100644 hostTools/lzma/compress/7z.h create mode 100644 hostTools/lzma/compress/7zapi.cpp create mode 100644 hostTools/lzma/compress/7zapi.h create mode 100644 hostTools/lzma/compress/7zlzma.cpp create mode 100644 hostTools/lzma/compress/AriBitCoder.cpp create mode 100644 hostTools/lzma/compress/AriBitCoder.h create mode 100644 hostTools/lzma/compress/AriConst.h create mode 100644 hostTools/lzma/compress/AriPrice.h create mode 100644 hostTools/lzma/compress/BinTree.h create mode 100644 hostTools/lzma/compress/BinTree2.h create mode 100644 hostTools/lzma/compress/BinTree2Main.h create mode 100644 hostTools/lzma/compress/BinTree3.h create mode 100644 hostTools/lzma/compress/BinTree3Main.h create mode 100644 hostTools/lzma/compress/BinTree3Z.h create mode 100644 hostTools/lzma/compress/BinTree3ZMain.h create mode 100644 hostTools/lzma/compress/BinTree4.h create mode 100644 hostTools/lzma/compress/BinTree4Main.h create mode 100644 hostTools/lzma/compress/BinTree4b.h create mode 100644 hostTools/lzma/compress/BinTree4bMain.h create mode 100644 hostTools/lzma/compress/BinTreeMF.h create mode 100644 hostTools/lzma/compress/BinTreeMFMain.h create mode 100644 hostTools/lzma/compress/BinTreeMain.h create mode 100644 hostTools/lzma/compress/BitTreeCoder.h create mode 100644 hostTools/lzma/compress/CRC.h create mode 100644 hostTools/lzma/compress/Const.h create mode 100644 hostTools/lzma/compress/IInOutStreams.cpp create mode 100644 hostTools/lzma/compress/IInOutStreams.h create mode 100644 hostTools/lzma/compress/InByte.cpp create mode 100644 hostTools/lzma/compress/InByte.h create mode 100644 hostTools/lzma/compress/LZMA.cpp create mode 100644 hostTools/lzma/compress/LZMA.h create mode 100644 hostTools/lzma/compress/LZMADecoder.cpp create mode 100644 hostTools/lzma/compress/LZMADecoder.h create mode 100644 hostTools/lzma/compress/LZMAEncoder.cpp create mode 100644 hostTools/lzma/compress/LZMAEncoder.h create mode 100644 hostTools/lzma/compress/LenCoder.cpp create mode 100644 hostTools/lzma/compress/LenCoder.h create mode 100644 hostTools/lzma/compress/LiteralCoder.cpp create mode 100644 hostTools/lzma/compress/LiteralCoder.h create mode 100644 hostTools/lzma/compress/OutByte.cpp create mode 100644 hostTools/lzma/compress/OutByte.h create mode 100644 hostTools/lzma/compress/Portable.h create mode 100644 hostTools/lzma/compress/RCDefs.h create mode 100644 hostTools/lzma/compress/RangeCoder.h create mode 100644 hostTools/lzma/compress/StdAfx.cpp create mode 100644 hostTools/lzma/compress/StdAfx.h create mode 100644 hostTools/lzma/compress/WindowIn.cpp create mode 100644 hostTools/lzma/compress/WindowIn.h create mode 100644 hostTools/lzma/compress/WindowOut.cpp create mode 100644 hostTools/lzma/compress/WindowOut.h create mode 100644 hostTools/lzma/compress/lzDecomp.cpp create mode 100644 hostTools/lzma/decompress/7z.h create mode 100644 hostTools/lzma/decompress/7zlzma.c create mode 100644 hostTools/lzma/decompress/AriBitCoder.h create mode 100644 hostTools/lzma/decompress/BitTreeCoder.h create mode 100644 hostTools/lzma/decompress/IInOutStreams.c create mode 100644 hostTools/lzma/decompress/IInOutStreams.h create mode 100644 hostTools/lzma/decompress/LZMA.h create mode 100644 hostTools/lzma/decompress/LZMADecoder.c create mode 100644 hostTools/lzma/decompress/LZMADecoder.h create mode 100644 hostTools/lzma/decompress/LenCoder.h create mode 100644 hostTools/lzma/decompress/LiteralCoder.h create mode 100644 hostTools/lzma/decompress/Makefile create mode 100644 hostTools/lzma/decompress/Portable.h create mode 100644 hostTools/lzma/decompress/RCDefs.h create mode 100644 hostTools/lzma/decompress/RangeCoder.h create mode 100644 hostTools/lzma/decompress/WindowOut.h create mode 100644 hostTools/lzma/decompress/vxTypesOld.h (limited to 'hostTools/lzma') diff --git a/hostTools/lzma/compress/7z.h b/hostTools/lzma/compress/7z.h new file mode 100644 index 0000000..241a2ea --- /dev/null +++ b/hostTools/lzma/compress/7z.h @@ -0,0 +1,12 @@ +#ifndef __7Z_H +#define __7Z_H + +bool compress_deflate_7z(const unsigned char* in_data, unsigned in_size, unsigned char* out_data, unsigned& out_size, unsigned num_passes, unsigned num_fast_bytes) throw (); +bool decompress_deflate_7z(const unsigned char* in_data, unsigned in_size, unsigned char* out_data, unsigned out_size) throw (); +bool compress_rfc1950_7z(const unsigned char* in_data, unsigned in_size, unsigned char* out_data, unsigned& out_size, unsigned num_passes, unsigned num_fast_bytes) throw (); + +bool compress_lzma_7z(const unsigned char* in_data, unsigned in_size, unsigned char* out_data, unsigned& out_size, unsigned algo, unsigned dictionary_size, unsigned num_fast_bytes) throw (); +bool decompress_lzma_7z(const unsigned char* in_data, unsigned in_size, unsigned char* out_data, unsigned out_size) throw (); + +#endif + diff --git a/hostTools/lzma/compress/7zapi.cpp b/hostTools/lzma/compress/7zapi.cpp new file mode 100644 index 0000000..cc6c908 --- /dev/null +++ b/hostTools/lzma/compress/7zapi.cpp @@ -0,0 +1,19 @@ +#include "7z.h" +/********************** APIs Definitions ************************************/ + +extern "C" { + +int compress_lzma_7zapi(const unsigned char* in_data, unsigned in_size, unsigned char* out_data, unsigned *out_size, unsigned algo, unsigned dictionary_size, unsigned num_fast_bytes); + +} + +int compress_lzma_7zapi(const unsigned char* in_data, unsigned in_size, unsigned char* out_data, unsigned *out_size, unsigned algo, unsigned dictionary_size, unsigned num_fast_bytes) +{ + bool ret; + //unsigned outsize = *out_size; + + ret = compress_lzma_7z(in_data, in_size, out_data, *out_size, algo, dictionary_size, num_fast_bytes); + + return (int)ret; +} + diff --git a/hostTools/lzma/compress/7zapi.h b/hostTools/lzma/compress/7zapi.h new file mode 100644 index 0000000..e2d6ac3 --- /dev/null +++ b/hostTools/lzma/compress/7zapi.h @@ -0,0 +1,16 @@ +#ifndef __7ZAPI_H__ +#define __7ZAPI_H__ + +#if defined(__cplusplus) +extern "C" { +#endif + +extern int compress_lzma_7zapi(const unsigned char* in_data, unsigned in_size, unsigned char* out_data, unsigned *out_size, unsigned algo, unsigned dictionary_size, unsigned num_fast_bytes); + + +#if defined(__cplusplus) +} +#endif + + +#endif diff --git a/hostTools/lzma/compress/7zlzma.cpp b/hostTools/lzma/compress/7zlzma.cpp new file mode 100644 index 0000000..35468c1 --- /dev/null +++ b/hostTools/lzma/compress/7zlzma.cpp @@ -0,0 +1,79 @@ +#include "7z.h" + +#include "LZMAEncoder.h" +#include "LZMADecoder.h" + +bool compress_lzma_7z(const unsigned char* in_data, + unsigned in_size, + unsigned char* out_data, + unsigned& out_size, + unsigned algo, + unsigned dictionary_size, + unsigned num_fast_bytes) throw () { + try { + NCompress::NLZMA::CEncoder cc; + + // reduce the dictionary size if the file is small + while (dictionary_size > 8 && dictionary_size / 2 >= out_size) + dictionary_size /= 2; + + if (cc.SetDictionarySize(dictionary_size) != S_OK) + return false; + + if (cc.SetEncoderNumFastBytes(num_fast_bytes) != S_OK) + return false; + + if (cc.SetEncoderAlgorithm(algo) != S_OK) + return false; + + ISequentialInStream in(reinterpret_cast(in_data), in_size); + ISequentialOutStream out(reinterpret_cast(out_data), out_size); + + UINT64 in_size_l = in_size; + + if (cc.WriteCoderProperties(&out) != S_OK) + return false; + + if (cc.Code(&in, &out, &in_size_l) != S_OK) + return false; + + out_size = out.size_get(); + + if (out.overflow_get()) + return false; + + return true; + } catch (...) { + return false; + } +} +#if 0 +bool decompress_lzma_7z(const unsigned char* in_data, + unsigned in_size, + unsigned char* out_data, + unsigned out_size) throw () { + try { + NCompress::NLZMA::CDecoder cc; + + ISequentialInStream in(reinterpret_cast(in_data), in_size); + ISequentialOutStream out(reinterpret_cast(out_data), out_size); + + UINT64 in_size_l = in_size; + UINT64 out_size_l = out_size; + + if (cc.ReadCoderProperties(&in) != S_OK) + return false; + + if (cc.Code(&in, &out, &in_size_l, &out_size_l) != S_OK) + return false; + + if (out.size_get() != out_size || out.overflow_get()) + return false; + + return true; + } catch (...) { + return false; + } +} +#endif + diff --git a/hostTools/lzma/compress/AriBitCoder.cpp b/hostTools/lzma/compress/AriBitCoder.cpp new file mode 100644 index 0000000..ade1888 --- /dev/null +++ b/hostTools/lzma/compress/AriBitCoder.cpp @@ -0,0 +1,21 @@ +#include "AriBitCoder.h" +#include "AriPrice.h" + +#include + +namespace NCompression { +namespace NArithmetic { + +static const double kDummyMultMid = (1.0 / kBitPrice) / 2; + +CPriceTables::CPriceTables() +{ + double aLn2 = log(2); + double aLnAll = log(kBitModelTotal >> kNumMoveReducingBits); + for(UINT32 i = 1; i < (kBitModelTotal >> kNumMoveReducingBits) - 1; i++) + m_StatePrices[i] = UINT32((fabs(aLnAll - log(i)) / aLn2 + kDummyMultMid) * kBitPrice); +} + +CPriceTables g_PriceTables; + +}} diff --git a/hostTools/lzma/compress/AriBitCoder.h b/hostTools/lzma/compress/AriBitCoder.h new file mode 100644 index 0000000..76328cd --- /dev/null +++ b/hostTools/lzma/compress/AriBitCoder.h @@ -0,0 +1,101 @@ +#ifndef __COMPRESSION_BITCODER_H +#define __COMPRESSION_BITCODER_H + +#include "RangeCoder.h" + +namespace NCompression { +namespace NArithmetic { + +const int kNumBitModelTotalBits = 11; +const UINT32 kBitModelTotal = (1 << kNumBitModelTotalBits); + +const int kNumMoveReducingBits = 2; + + +class CPriceTables +{ +public: + UINT32 m_StatePrices[kBitModelTotal >> kNumMoveReducingBits]; + CPriceTables(); +}; + +extern CPriceTables g_PriceTables; + + +///////////////////////////// +// CBitModel + +template +class CBitModel +{ +public: + UINT32 m_Probability; + void UpdateModel(UINT32 aSymbol) + { + /* + m_Probability -= (m_Probability + ((aSymbol - 1) & ((1 << aNumMoveBits) - 1))) >> aNumMoveBits; + m_Probability += (1 - aSymbol) << (kNumBitModelTotalBits - aNumMoveBits); + */ + if (aSymbol == 0) + m_Probability += (kBitModelTotal - m_Probability) >> aNumMoveBits; + else + m_Probability -= (m_Probability) >> aNumMoveBits; + } +public: + void Init() { m_Probability = kBitModelTotal / 2; } +}; + +template +class CBitEncoder: public CBitModel +{ +public: + void Encode(CRangeEncoder *aRangeEncoder, UINT32 aSymbol) + { + aRangeEncoder->EncodeBit(this->m_Probability, kNumBitModelTotalBits, aSymbol); + this->UpdateModel(aSymbol); + } + UINT32 GetPrice(UINT32 aSymbol) const + { + return g_PriceTables.m_StatePrices[ + (((this->m_Probability - aSymbol) ^ ((-(int)aSymbol))) & (kBitModelTotal - 1)) >> kNumMoveReducingBits]; + } +}; + + +template +class CBitDecoder: public CBitModel +{ +public: + UINT32 Decode(CRangeDecoder *aRangeDecoder) + { + UINT32 aNewBound = (aRangeDecoder->m_Range >> kNumBitModelTotalBits) * this->m_Probability; + if (aRangeDecoder->m_Code < aNewBound) + { + aRangeDecoder->m_Range = aNewBound; + this->m_Probability += (kBitModelTotal - this->m_Probability) >> aNumMoveBits; + if (aRangeDecoder->m_Range < kTopValue) + { + aRangeDecoder->m_Code = (aRangeDecoder->m_Code << 8) | aRangeDecoder->m_Stream.ReadByte(); + aRangeDecoder->m_Range <<= 8; + } + return 0; + } + else + { + aRangeDecoder->m_Range -= aNewBound; + aRangeDecoder->m_Code -= aNewBound; + this->m_Probability -= (this->m_Probability) >> aNumMoveBits; + if (aRangeDecoder->m_Range < kTopValue) + { + aRangeDecoder->m_Code = (aRangeDecoder->m_Code << 8) | aRangeDecoder->m_Stream.ReadByte(); + aRangeDecoder->m_Range <<= 8; + } + return 1; + } + } +}; + +}} + + +#endif diff --git a/hostTools/lzma/compress/AriConst.h b/hostTools/lzma/compress/AriConst.h new file mode 100644 index 0000000..1e429dd --- /dev/null +++ b/hostTools/lzma/compress/AriConst.h @@ -0,0 +1,17 @@ +#ifndef __ARICONST_H +#define __ARICONST_H + +#include "AriBitCoder.h" + +typedef NCompression::NArithmetic::CRangeEncoder CMyRangeEncoder; +typedef NCompression::NArithmetic::CRangeDecoder CMyRangeDecoder; + +template class CMyBitEncoder: + public NCompression::NArithmetic::CBitEncoder {}; +template class CMyBitDecoder: + public NCompression::NArithmetic::CBitDecoder {}; + +#endif + + + diff --git a/hostTools/lzma/compress/AriPrice.h b/hostTools/lzma/compress/AriPrice.h new file mode 100644 index 0000000..ccc398e --- /dev/null +++ b/hostTools/lzma/compress/AriPrice.h @@ -0,0 +1,12 @@ +#ifndef __COMPRESSION_ARIPRICE_H +#define __COMPRESSION_ARIPRICE_H + +namespace NCompression { +namespace NArithmetic { + +const UINT32 kNumBitPriceShiftBits = 6; +const UINT32 kBitPrice = 1 << kNumBitPriceShiftBits; + +}} + +#endif diff --git a/hostTools/lzma/compress/BinTree.h b/hostTools/lzma/compress/BinTree.h new file mode 100644 index 0000000..29c273d --- /dev/null +++ b/hostTools/lzma/compress/BinTree.h @@ -0,0 +1,64 @@ +#include "Portable.h" +#include "WindowIn.h" + +namespace BT_NAMESPACE { + +typedef UINT32 CIndex; +const UINT32 kMaxValForNormalize = (UINT32(1) << 31) - 1; + +struct CPair +{ + CIndex Left; + CIndex Right; +}; + +class CInTree: public NStream::NWindow::CIn +{ + UINT32 m_HistorySize; + UINT32 m_MatchMaxLen; + + CIndex *m_Hash; + + #ifdef HASH_ARRAY_2 + CIndex *m_Hash2; + #ifdef HASH_ARRAY_3 + CIndex *m_Hash3; + #endif + #endif + + CPair *m_Son; + CPair *m_Base; + + UINT32 m_CutValue; + + void NormalizeLinks(CIndex *anArray, UINT32 aNumItems, UINT32 aSubValue); + void Normalize(); + void FreeMemory(); + +protected: + virtual void AfterMoveBlock(); +public: + CInTree(); + ~CInTree(); + HRESULT Create(UINT32 aSizeHistory, UINT32 aKeepAddBufferBefore, UINT32 aMatchMaxLen, + UINT32 aKeepAddBufferAfter, UINT32 _dwSizeReserv = (1<<17)); + HRESULT Init(ISequentialInStream *aStream); + void SetCutValue(UINT32 aCutValue) { m_CutValue = aCutValue; } + UINT32 GetLongestMatch(UINT32 *aDistances); + void DummyLongestMatch(); + HRESULT MovePos() + { + RETURN_IF_NOT_S_OK(CIn::MovePos()); + if (m_Pos == kMaxValForNormalize) + Normalize(); + return S_OK; + } + void ReduceOffsets(UINT32 aSubValue) + { + CIn::ReduceOffsets(aSubValue); + m_Son += aSubValue; + } +}; + +} + diff --git a/hostTools/lzma/compress/BinTree2.h b/hostTools/lzma/compress/BinTree2.h new file mode 100644 index 0000000..7953d06 --- /dev/null +++ b/hostTools/lzma/compress/BinTree2.h @@ -0,0 +1,13 @@ +#ifndef __BINTREE2__H +#define __BINTREE2__H + +#undef BT_CLSID +#define BT_CLSID CLSID_CMatchFinderBT2 + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT2 + +#include "BinTreeMF.h" + +#endif + diff --git a/hostTools/lzma/compress/BinTree2Main.h b/hostTools/lzma/compress/BinTree2Main.h new file mode 100644 index 0000000..385166e --- /dev/null +++ b/hostTools/lzma/compress/BinTree2Main.h @@ -0,0 +1,13 @@ +#ifndef __BINTREE2MAIN__H +#define __BINTREE2MAIN__H + +#undef BT_CLSID +#define BT_CLSID CLSID_CMatchFinderBT2 + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT2 + +#include "BinTreeMFMain.h" + +#endif + diff --git a/hostTools/lzma/compress/BinTree3.h b/hostTools/lzma/compress/BinTree3.h new file mode 100644 index 0000000..320a619 --- /dev/null +++ b/hostTools/lzma/compress/BinTree3.h @@ -0,0 +1,17 @@ +#ifndef __BINTREE3__H +#define __BINTREE3__H + +#undef BT_CLSID +#define BT_CLSID CLSID_CMatchFinderBT3 + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT3 + +#define HASH_ARRAY_2 + +#include "BinTreeMF.h" + +#undef HASH_ARRAY_2 + +#endif + diff --git a/hostTools/lzma/compress/BinTree3Main.h b/hostTools/lzma/compress/BinTree3Main.h new file mode 100644 index 0000000..6331084 --- /dev/null +++ b/hostTools/lzma/compress/BinTree3Main.h @@ -0,0 +1,17 @@ +#ifndef __BINTREE3MAIN__H +#define __BINTREE3MAIN__H + +#undef BT_CLSID +#define BT_CLSID CLSID_CMatchFinderBT3 + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT3 + +#define HASH_ARRAY_2 + +#include "BinTreeMFMain.h" + +#undef HASH_ARRAY_2 + +#endif + diff --git a/hostTools/lzma/compress/BinTree3Z.h b/hostTools/lzma/compress/BinTree3Z.h new file mode 100644 index 0000000..cf65c7f --- /dev/null +++ b/hostTools/lzma/compress/BinTree3Z.h @@ -0,0 +1,14 @@ +#ifndef __BINTREE3Z__H +#define __BINTREE3Z__H + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT3Z + +#define HASH_ZIP + +#include "BinTree.h" + +#undef HASH_ZIP + +#endif + diff --git a/hostTools/lzma/compress/BinTree3ZMain.h b/hostTools/lzma/compress/BinTree3ZMain.h new file mode 100644 index 0000000..eb9e080 --- /dev/null +++ b/hostTools/lzma/compress/BinTree3ZMain.h @@ -0,0 +1,14 @@ +#ifndef __BINTREE3ZMAIN__H +#define __BINTREE3ZMAIN__H + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT3Z + +#define HASH_ZIP + +#include "BinTreeMain.h" + +#undef HASH_ZIP + +#endif + diff --git a/hostTools/lzma/compress/BinTree4.h b/hostTools/lzma/compress/BinTree4.h new file mode 100644 index 0000000..6af6978 --- /dev/null +++ b/hostTools/lzma/compress/BinTree4.h @@ -0,0 +1,19 @@ +#ifndef __BINTREE4__H +#define __BINTREE4__H + +#undef BT_CLSID +#define BT_CLSID CLSID_CMatchFinderBT4 + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT4 + +#define HASH_ARRAY_2 +#define HASH_ARRAY_3 + +#include "BinTreeMF.h" + +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 + +#endif + diff --git a/hostTools/lzma/compress/BinTree4Main.h b/hostTools/lzma/compress/BinTree4Main.h new file mode 100644 index 0000000..f8e2e22 --- /dev/null +++ b/hostTools/lzma/compress/BinTree4Main.h @@ -0,0 +1,19 @@ +#ifndef __BINTREEMAIN4__H +#define __BINTREEMAIN4__H + +#undef BT_CLSID +#define BT_CLSID CLSID_CMatchFinderBT4 + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT4 + +#define HASH_ARRAY_2 +#define HASH_ARRAY_3 + +#include "BinTreeMFMain.h" + +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 + +#endif + diff --git a/hostTools/lzma/compress/BinTree4b.h b/hostTools/lzma/compress/BinTree4b.h new file mode 100644 index 0000000..7b68754 --- /dev/null +++ b/hostTools/lzma/compress/BinTree4b.h @@ -0,0 +1,21 @@ +#ifndef __BINTREE4B__H +#define __BINTREE4B__H + +#undef BT_CLSID +#define BT_CLSID CLSID_CMatchFinderBT4b + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT4b + +#define HASH_ARRAY_2 +#define HASH_ARRAY_3 +#define HASH_BIG + +#include "BinTreeMF.h" + +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 +#undef HASH_BIG + +#endif + diff --git a/hostTools/lzma/compress/BinTree4bMain.h b/hostTools/lzma/compress/BinTree4bMain.h new file mode 100644 index 0000000..b707ca1 --- /dev/null +++ b/hostTools/lzma/compress/BinTree4bMain.h @@ -0,0 +1,21 @@ +#ifndef __BINTREE4BMAIN__H +#define __BINTREE4BMAIN__H + +#undef BT_CLSID +#define BT_CLSID CLSID_CMatchFinderBT4b + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT4b + +#define HASH_ARRAY_2 +#define HASH_ARRAY_3 +#define HASH_BIG + +#include "BinTreeMFMain.h" + +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 +#undef HASH_BIG + +#endif + diff --git a/hostTools/lzma/compress/BinTreeMF.h b/hostTools/lzma/compress/BinTreeMF.h new file mode 100644 index 0000000..8019ab5 --- /dev/null +++ b/hostTools/lzma/compress/BinTreeMF.h @@ -0,0 +1,19 @@ +// #ifndef __BINTREEMF_H +// #define __BINTREEMF_H + +#include "BinTree.h" + +namespace BT_NAMESPACE { + +class CMatchFinderBinTree : public CInTree +{ +public: + HRESULT Create(UINT32 aSizeHistory, + UINT32 aKeepAddBufferBefore, UINT32 aMatchMaxLen, + UINT32 aKeepAddBufferAfter); +}; + +} + +// #endif + diff --git a/hostTools/lzma/compress/BinTreeMFMain.h b/hostTools/lzma/compress/BinTreeMFMain.h new file mode 100644 index 0000000..5438093 --- /dev/null +++ b/hostTools/lzma/compress/BinTreeMFMain.h @@ -0,0 +1,30 @@ +#include "BinTreeMain.h" + +namespace BT_NAMESPACE { + +HRESULT CMatchFinderBinTree::Create(UINT32 aSizeHistory, + UINT32 aKeepAddBufferBefore, UINT32 aMatchMaxLen, + UINT32 aKeepAddBufferAfter) +{ + const UINT32 kAlignMask = (1 << 16) - 1; + UINT32 aWindowReservSize = aSizeHistory / 2; + aWindowReservSize += kAlignMask; + aWindowReservSize &= ~(kAlignMask); + + const int kMinDictSize = (1 << 19); + if (aWindowReservSize < kMinDictSize) + aWindowReservSize = kMinDictSize; + aWindowReservSize += 256; + + try + { + return CInTree::Create(aSizeHistory, aKeepAddBufferBefore, aMatchMaxLen, + aKeepAddBufferAfter, aWindowReservSize); + } + catch(...) + { + return E_OUTOFMEMORY; + } +} + +} diff --git a/hostTools/lzma/compress/BinTreeMain.h b/hostTools/lzma/compress/BinTreeMain.h new file mode 100644 index 0000000..f452a94 --- /dev/null +++ b/hostTools/lzma/compress/BinTreeMain.h @@ -0,0 +1,502 @@ +#include "CRC.h" + +namespace BT_NAMESPACE { + +#ifdef HASH_ARRAY_2 + static const UINT32 kHash2Size = 1 << 10; + #ifdef HASH_ARRAY_3 + static const UINT32 kNumHashDirectBytes = 0; + static const UINT32 kNumHashBytes = 4; + static const UINT32 kHash3Size = 1 << 18; + #ifdef HASH_BIG + static const UINT32 kHashSize = 1 << 23; + #else + static const UINT32 kHashSize = 1 << 20; + #endif + #else + static const UINT32 kNumHashDirectBytes = 3; + static const UINT32 kNumHashBytes = 3; + static const UINT32 kHashSize = 1 << (8 * kNumHashBytes); + #endif +#else + #ifdef HASH_ZIP + static const UINT32 kNumHashDirectBytes = 0; + static const UINT32 kNumHashBytes = 3; + static const UINT32 kHashSize = 1 << 16; + #else + static const UINT32 kNumHashDirectBytes = 2; + static const UINT32 kNumHashBytes = 2; + static const UINT32 kHashSize = 1 << (8 * kNumHashBytes); + #endif +#endif + +CInTree::CInTree(): + #ifdef HASH_ARRAY_2 + m_Hash2(0), + #ifdef HASH_ARRAY_3 + m_Hash3(0), + #endif + #endif + m_Hash(0), + m_Base(0), + m_CutValue(0xFF) +{ +} + +void CInTree::FreeMemory() +{ + if (m_Base != 0) + delete [] m_Base; + if (m_Hash != 0) + delete [] m_Hash; + m_Base = 0; + m_Hash = 0; + CIn::Free(); +} + +CInTree::~CInTree() +{ + FreeMemory(); +} + +HRESULT CInTree::Create(UINT32 aSizeHistory, UINT32 aKeepAddBufferBefore, + UINT32 aMatchMaxLen, UINT32 aKeepAddBufferAfter, UINT32 aSizeReserv) +{ + FreeMemory(); + CIn::Create(aSizeHistory + aKeepAddBufferBefore, + aMatchMaxLen + aKeepAddBufferAfter, aSizeReserv); + + if (m_BlockSize + 256 > kMaxValForNormalize) + return E_INVALIDARG; + + m_HistorySize = aSizeHistory; + m_MatchMaxLen = aMatchMaxLen; + + + UINT32 aSize = kHashSize; + #ifdef HASH_ARRAY_2 + aSize += kHash2Size; + #ifdef HASH_ARRAY_3 + aSize += kHash3Size; + #endif + #endif + + m_Base = new CPair[m_BlockSize + 1]; + if (m_Base == 0) + return E_OUTOFMEMORY; + m_Hash = new CIndex[aSize + 1]; + if (m_Hash == 0) + return E_OUTOFMEMORY; + + #ifdef HASH_ARRAY_2 + m_Hash2 = &m_Hash[kHashSize]; + #ifdef HASH_ARRAY_3 + m_Hash3 = &m_Hash2[kHash2Size]; + #endif + #endif + return S_OK; +} + +static const UINT32 kEmptyHashValue = 0; + +HRESULT CInTree::Init(ISequentialInStream *aStream) +{ + RETURN_IF_NOT_S_OK(CIn::Init(aStream)); + unsigned i; + for(i = 0; i < kHashSize; i++) + m_Hash[i] = kEmptyHashValue; + + #ifdef HASH_ARRAY_2 + for(i = 0; i < kHash2Size; i++) + m_Hash2[i] = kEmptyHashValue; + #ifdef HASH_ARRAY_3 + for(i = 0; i < kHash3Size; i++) + m_Hash3[i] = kEmptyHashValue; + #endif + #endif + + m_Son = m_Base; + + ReduceOffsets(0 - 1); + return S_OK; +} + + +#ifdef HASH_ARRAY_2 +#ifdef HASH_ARRAY_3 +inline UINT32 Hash(const BYTE *aPointer, UINT32 &aHash2Value, UINT32 &aHash3Value) +{ + UINT32 aTemp = CCRC::m_Table[aPointer[0]] ^ aPointer[1]; + aHash2Value = aTemp & (kHash2Size - 1); + aHash3Value = (aTemp ^ (UINT32(aPointer[2]) << 8)) & (kHash3Size - 1); + return (aTemp ^ (UINT32(aPointer[2]) << 8) ^ (CCRC::m_Table[aPointer[3]] << 5)) & + (kHashSize - 1); +} +#else // no HASH_ARRAY_3 +inline UINT32 Hash(const BYTE *aPointer, UINT32 &aHash2Value) +{ + aHash2Value = (CCRC::m_Table[aPointer[0]] ^ aPointer[1]) & (kHash2Size - 1); + return (*((const UINT32 *)aPointer)) & 0xFFFFFF; +} +#endif // HASH_ARRAY_3 +#else // no HASH_ARRAY_2 +#ifdef HASH_ZIP +inline UINT32 Hash(const BYTE *aPointer) +{ + return ((UINT32(aPointer[0]) << 8) ^ + CCRC::m_Table[aPointer[1]] ^ aPointer[2]) & (kHashSize - 1); +} +#else // no HASH_ZIP +inline UINT32 Hash(const BYTE *aPointer) +{ + return aPointer[0] ^ (UINT32(aPointer[1]) << 8); +} +#endif // HASH_ZIP +#endif // HASH_ARRAY_2 + +UINT32 CInTree::GetLongestMatch(UINT32 *aDistances) +{ + UINT32 aCurrentLimit; + if (m_Pos + m_MatchMaxLen <= m_StreamPos) + aCurrentLimit = m_MatchMaxLen; + else + { + aCurrentLimit = m_StreamPos - m_Pos; + if(aCurrentLimit < kNumHashBytes) + return 0; + } + + UINT32 aMatchMinPos = (m_Pos > m_HistorySize) ? (m_Pos - m_HistorySize) : 1; + BYTE *aCur = m_Buffer + m_Pos; + + UINT32 aMatchHashLenMax = 0; + + #ifdef HASH_ARRAY_2 + UINT32 aHash2Value; + #ifdef HASH_ARRAY_3 + UINT32 aHash3Value; + UINT32 aHashValue = Hash(aCur, aHash2Value, aHash3Value); + #else + UINT32 aHashValue = Hash(aCur, aHash2Value); + #endif + #else + UINT32 aHashValue = Hash(aCur); + #endif + + UINT32 aCurMatch = m_Hash[aHashValue]; + #ifdef HASH_ARRAY_2 + UINT32 aCurMatch2 = m_Hash2[aHash2Value]; + #ifdef HASH_ARRAY_3 + UINT32 aCurMatch3 = m_Hash3[aHash3Value]; + #endif + m_Hash2[aHash2Value] = m_Pos; + bool aMatchLen2Exist = false; + UINT32 aLen2Distance = 0; + if(aCurMatch2 >= aMatchMinPos) + { + if (m_Buffer[aCurMatch2] == aCur[0]) + { + aLen2Distance = m_Pos - aCurMatch2 - 1; + aMatchHashLenMax = 2; + aMatchLen2Exist = true; + } + } + + #ifdef HASH_ARRAY_3 + m_Hash3[aHash3Value] = m_Pos; + UINT32 aMatchLen3Exist = false; + UINT32 aLen3Distance = 0; + if(aCurMatch3 >= aMatchMinPos) + { + if (m_Buffer[aCurMatch3] == aCur[0]) + { + aLen3Distance = m_Pos - aCurMatch3 - 1; + aMatchHashLenMax = 3; + aMatchLen3Exist = true; + if (aMatchLen2Exist) + { + if (aLen3Distance < aLen2Distance) + aLen2Distance = aLen3Distance; + } + else + { + aLen2Distance = aLen3Distance; + aMatchLen2Exist = true; + } + } + } + #endif + #endif + + m_Hash[aHashValue] = m_Pos; + if(aCurMatch < aMatchMinPos) + { + m_Son[m_Pos].Left = kEmptyHashValue; + m_Son[m_Pos].Right = kEmptyHashValue; + + #ifdef HASH_ARRAY_2 + aDistances[2] = aLen2Distance; + #ifdef HASH_ARRAY_3 + aDistances[3] = aLen3Distance; + #endif + #endif + + return aMatchHashLenMax; + } + CIndex *aPtrLeft = &m_Son[m_Pos].Right; + CIndex *aPtrRight = &m_Son[m_Pos].Left; + + UINT32 aMax, aMinSameLeft, aMinSameRight, aMinSame; + aMax = aMinSameLeft = aMinSameRight = aMinSame = kNumHashDirectBytes; + + #ifdef HASH_ARRAY_2 + #ifndef HASH_ARRAY_3 + if (aMatchLen2Exist) + aDistances[2] = aLen2Distance; + else + if (kNumHashDirectBytes >= 2) + aDistances[2] = m_Pos - aCurMatch - 1; + #endif + #endif + + aDistances[aMax] = m_Pos - aCurMatch - 1; + + for(UINT32 aCount = m_CutValue; aCount > 0; aCount--) + { + BYTE *pby1 = m_Buffer + aCurMatch; + // CIndex aLeft = m_Son[aCurMatch].Left; // it's prefetch + UINT32 aCurrentLen; + for(aCurrentLen = aMinSame; aCurrentLen < aCurrentLimit; aCurrentLen++/*, dwComps++*/) + if (pby1[aCurrentLen] != aCur[aCurrentLen]) + break; + while (aCurrentLen > aMax) + aDistances[++aMax] = m_Pos - aCurMatch - 1; + if (aCurrentLen != aCurrentLimit) + { + if (pby1[aCurrentLen] < aCur[aCurrentLen]) + { + *aPtrRight = aCurMatch; + aPtrRight = &m_Son[aCurMatch].Right; + aCurMatch = m_Son[aCurMatch].Right; + if(aCurrentLen > aMinSameLeft) + { + aMinSameLeft = aCurrentLen; + aMinSame = MyMin(aMinSameLeft, aMinSameRight); + } + } + else + { + *aPtrLeft = aCurMatch; + aPtrLeft = &m_Son[aCurMatch].Left; + // aCurMatch = aLeft; + aCurMatch = m_Son[aCurMatch].Left; + if(aCurrentLen > aMinSameRight) + { + aMinSameRight = aCurrentLen; + aMinSame = MyMin(aMinSameLeft, aMinSameRight); + } + } + } + else + { + if(aCurrentLen < m_MatchMaxLen) + { + *aPtrLeft = aCurMatch; + aPtrLeft = &m_Son[aCurMatch].Left; + aCurMatch = m_Son[aCurMatch].Left; + if(aCurrentLen > aMinSameRight) + { + aMinSameRight = aCurrentLen; + aMinSame = MyMin(aMinSameLeft, aMinSameRight); + } + } + else + { + *aPtrLeft = m_Son[aCurMatch].Right; + *aPtrRight = m_Son[aCurMatch].Left; + + #ifdef HASH_ARRAY_2 + if (aMatchLen2Exist && aLen2Distance < aDistances[2]) + aDistances[2] = aLen2Distance; + #ifdef HASH_ARRAY_3 + if (aMatchLen3Exist && aLen3Distance < aDistances[3]) + aDistances[3] = aLen3Distance; + #endif + #endif + + return aMax; + } + } + if(aCurMatch < aMatchMinPos) + break; + } + *aPtrLeft = kEmptyHashValue; + *aPtrRight = kEmptyHashValue; + #ifdef HASH_ARRAY_2 + if (aMatchLen2Exist) + { + if (aMax < 2) + { + aDistances[2] = aLen2Distance; + aMax = 2; + } + else if (aLen2Distance < aDistances[2]) + aDistances[2] = aLen2Distance; + } + #ifdef HASH_ARRAY_3 + if (aMatchLen3Exist) + { + if (aMax < 3) + { + aDistances[3] = aLen3Distance; + aMax = 3; + } + else if (aLen3Distance < aDistances[3]) + aDistances[3] = aLen3Distance; + } + #endif + #endif + return aMax; +} + +void CInTree::DummyLongestMatch() +{ + UINT32 aCurrentLimit; + if (m_Pos + m_MatchMaxLen <= m_StreamPos) + aCurrentLimit = m_MatchMaxLen; + else + { + aCurrentLimit = m_StreamPos - m_Pos; + if(aCurrentLimit < kNumHashBytes) + return; + } + UINT32 aMatchMinPos = (m_Pos > m_HistorySize) ? (m_Pos - m_HistorySize) : 1; + BYTE *aCur = m_Buffer + m_Pos; + + #ifdef HASH_ARRAY_2 + UINT32 aHash2Value; + #ifdef HASH_ARRAY_3 + UINT32 aHash3Value; + UINT32 aHashValue = Hash(aCur, aHash2Value, aHash3Value); + m_Hash3[aHash3Value] = m_Pos; + #else + UINT32 aHashValue = Hash(aCur, aHash2Value); + #endif + m_Hash2[aHash2Value] = m_Pos; + #else + UINT32 aHashValue = Hash(aCur); + #endif + + UINT32 aCurMatch = m_Hash[aHashValue]; + m_Hash[aHashValue] = m_Pos; + if(aCurMatch < aMatchMinPos) + { + m_Son[m_Pos].Left = kEmptyHashValue; + m_Son[m_Pos].Right = kEmptyHashValue; + return; + } + CIndex *aPtrLeft = &m_Son[m_Pos].Right; + CIndex *aPtrRight = &m_Son[m_Pos].Left; + + UINT32 aMax, aMinSameLeft, aMinSameRight, aMinSame; + aMax = aMinSameLeft = aMinSameRight = aMinSame = kNumHashDirectBytes; + for(UINT32 aCount = m_CutValue; aCount > 0; aCount--) + { + BYTE *pby1 = m_Buffer + aCurMatch; + // CIndex aLeft = m_Son[aCurMatch].Left; // it's prefetch + UINT32 aCurrentLen; + for(aCurrentLen = aMinSame; aCurrentLen < aCurrentLimit; aCurrentLen++/*, dwComps++*/) + if (pby1[aCurrentLen] != aCur[aCurrentLen]) + break; + if (aCurrentLen != aCurrentLimit) + { + if (pby1[aCurrentLen] < aCur[aCurrentLen]) + { + *aPtrRight = aCurMatch; + aPtrRight = &m_Son[aCurMatch].Right; + aCurMatch = m_Son[aCurMatch].Right; + if(aCurrentLen > aMinSameLeft) + { + aMinSameLeft = aCurrentLen; + aMinSame = MyMin(aMinSameLeft, aMinSameRight); + } + } + else + { + *aPtrLeft = aCurMatch; + aPtrLeft = &m_Son[aCurMatch].Left; + aCurMatch = m_Son[aCurMatch].Left; + // aCurMatch = aLeft; + if(aCurrentLen > aMinSameRight) + { + aMinSameRight = aCurrentLen; + aMinSame = MyMin(aMinSameLeft, aMinSameRight); + } + } + } + else + { + if(aCurrentLen < m_MatchMaxLen) + { + *aPtrLeft = aCurMatch; + aPtrLeft = &m_Son[aCurMatch].Left; + aCurMatch = m_Son[aCurMatch].Left; + if(aCurrentLen > aMinSameRight) + { + aMinSameRight = aCurrentLen; + aMinSame = MyMin(aMinSameLeft, aMinSameRight); + } + } + else + { + *aPtrLeft = m_Son[aCurMatch].Right; + *aPtrRight = m_Son[aCurMatch].Left; + return; + } + } + if(aCurMatch < aMatchMinPos) + break; + } + *aPtrLeft = kEmptyHashValue; + *aPtrRight = kEmptyHashValue; +} + +void CInTree::AfterMoveBlock() +{ + UINT32 aNumBytesToMove = m_HistorySize * sizeof(CPair); + UINT32 aSpecOffset = ((m_Son + m_Pos) - m_Base) - m_HistorySize; + memmove(m_Base, m_Base + aSpecOffset, aNumBytesToMove); + m_Son -= aSpecOffset; +} + +void CInTree::NormalizeLinks(CIndex *anArray, UINT32 aNumItems, UINT32 aSubValue) +{ + for (UINT32 i = 0; i < aNumItems; i++) + { + UINT32 aValue = anArray[i]; + if (aValue <= aSubValue) + aValue = kEmptyHashValue; + else + aValue -= aSubValue; + anArray[i] = aValue; + } +} + +void CInTree::Normalize() +{ + UINT32 aStartItem = m_Pos - m_HistorySize; + UINT32 aSubValue = aStartItem - 1; + NormalizeLinks((CIndex *)(m_Son + aStartItem), m_HistorySize * 2, aSubValue); + NormalizeLinks(m_Hash, kHashSize, aSubValue); + + #ifdef HASH_ARRAY_2 + NormalizeLinks(m_Hash2, kHash2Size, aSubValue); + #ifdef HASH_ARRAY_3 + NormalizeLinks(m_Hash3, kHash3Size, aSubValue); + #endif + #endif + + ReduceOffsets(aSubValue); +} + +} diff --git a/hostTools/lzma/compress/BitTreeCoder.h b/hostTools/lzma/compress/BitTreeCoder.h new file mode 100644 index 0000000..a77f32f --- /dev/null +++ b/hostTools/lzma/compress/BitTreeCoder.h @@ -0,0 +1,290 @@ +#ifndef __BITTREECODER_H +#define __BITTREECODER_H + +#include "AriBitCoder.h" +#include "RCDefs.h" + +////////////////////////// +// CBitTreeEncoder + +template +class CBitTreeEncoder +{ + CMyBitEncoder m_Models[1 << m_NumBitLevels]; +public: + void Init() + { + for(UINT32 i = 1; i < (1 << m_NumBitLevels); i++) + m_Models[i].Init(); + } + void Encode(CMyRangeEncoder *aRangeEncoder, UINT32 aSymbol) + { + UINT32 aModelIndex = 1; + for (UINT32 aBitIndex = m_NumBitLevels; aBitIndex > 0 ;) + { + aBitIndex--; + UINT32 aBit = (aSymbol >> aBitIndex ) & 1; + m_Models[aModelIndex].Encode(aRangeEncoder, aBit); + aModelIndex = (aModelIndex << 1) | aBit; + } + }; + UINT32 GetPrice(UINT32 aSymbol) const + { + UINT32 aPrice = 0; + UINT32 aModelIndex = 1; + for (UINT32 aBitIndex = m_NumBitLevels; aBitIndex > 0 ;) + { + aBitIndex--; + UINT32 aBit = (aSymbol >> aBitIndex ) & 1; + aPrice += m_Models[aModelIndex].GetPrice(aBit); + aModelIndex = (aModelIndex << 1) + aBit; + } + return aPrice; + } +}; + +////////////////////////// +// CBitTreeDecoder + +template +class CBitTreeDecoder +{ + CMyBitDecoder m_Models[1 << m_NumBitLevels]; +public: + void Init() + { + for(UINT32 i = 1; i < (1 << m_NumBitLevels); i++) + m_Models[i].Init(); + } + UINT32 Decode(CMyRangeDecoder *aRangeDecoder) + { + UINT32 aModelIndex = 1; + RC_INIT_VAR + for(UINT32 aBitIndex = m_NumBitLevels; aBitIndex > 0; aBitIndex--) + { + // aModelIndex = (aModelIndex << 1) + m_Models[aModelIndex].Decode(aRangeDecoder); + RC_GETBIT(aNumMoveBits, m_Models[aModelIndex].m_Probability, aModelIndex) + } + RC_FLUSH_VAR + return aModelIndex - (1 << m_NumBitLevels); + }; +}; + + + +//////////////////////////////// +// CReverseBitTreeEncoder + +template +class CReverseBitTreeEncoder2 +{ + CMyBitEncoder *m_Models; + UINT32 m_NumBitLevels; +public: + CReverseBitTreeEncoder2(): m_Models(0) { } + ~CReverseBitTreeEncoder2() { delete []m_Models; } + bool Create(UINT32 aNumBitLevels) + { + m_NumBitLevels = aNumBitLevels; + m_Models = new CMyBitEncoder[1 << aNumBitLevels]; + return (m_Models != 0); + } + void Init() + { + UINT32 aNumModels = 1 << m_NumBitLevels; + for(UINT32 i = 1; i < aNumModels; i++) + m_Models[i].Init(); + } + void Encode(CMyRangeEncoder *aRangeEncoder, UINT32 aSymbol) + { + UINT32 aModelIndex = 1; + for (UINT32 i = 0; i < m_NumBitLevels; i++) + { + UINT32 aBit = aSymbol & 1; + m_Models[aModelIndex].Encode(aRangeEncoder, aBit); + aModelIndex = (aModelIndex << 1) | aBit; + aSymbol >>= 1; + } + } + UINT32 GetPrice(UINT32 aSymbol) const + { + UINT32 aPrice = 0; + UINT32 aModelIndex = 1; + for (UINT32 i = m_NumBitLevels; i > 0; i--) + { + UINT32 aBit = aSymbol & 1; + aSymbol >>= 1; + aPrice += m_Models[aModelIndex].GetPrice(aBit); + aModelIndex = (aModelIndex << 1) | aBit; + } + return aPrice; + } +}; + +/* +template +class CReverseBitTreeEncoder: public CReverseBitTreeEncoder2 +{ +public: + CReverseBitTreeEncoder() + { Create(aNumBitLevels); } +}; +*/ +//////////////////////////////// +// CReverseBitTreeDecoder + +template +class CReverseBitTreeDecoder2 +{ + CMyBitDecoder *m_Models; + UINT32 m_NumBitLevels; +public: + CReverseBitTreeDecoder2(): m_Models(0) { } + ~CReverseBitTreeDecoder2() { delete []m_Models; } + bool Create(UINT32 aNumBitLevels) + { + m_NumBitLevels = aNumBitLevels; + m_Models = new CMyBitDecoder[1 << aNumBitLevels]; + return (m_Models != 0); + } + void Init() + { + UINT32 aNumModels = 1 << m_NumBitLevels; + for(UINT32 i = 1; i < aNumModels; i++) + m_Models[i].Init(); + } + UINT32 Decode(CMyRangeDecoder *aRangeDecoder) + { + UINT32 aModelIndex = 1; + UINT32 aSymbol = 0; + RC_INIT_VAR + for(UINT32 aBitIndex = 0; aBitIndex < m_NumBitLevels; aBitIndex++) + { + // UINT32 aBit = m_Models[aModelIndex].Decode(aRangeDecoder); + // aModelIndex <<= 1; + // aModelIndex += aBit; + // aSymbol |= (aBit << aBitIndex); + RC_GETBIT2(aNumMoveBits, m_Models[aModelIndex].m_Probability, aModelIndex, ; , aSymbol |= (1 << aBitIndex)) + } + RC_FLUSH_VAR + return aSymbol; + }; +}; +//////////////////////////// +// CReverseBitTreeDecoder2 + +template +class CReverseBitTreeDecoder +{ + CMyBitDecoder m_Models[1 << m_NumBitLevels]; +public: + void Init() + { + for(UINT32 i = 1; i < (1 << m_NumBitLevels); i++) + m_Models[i].Init(); + } + UINT32 Decode(CMyRangeDecoder *aRangeDecoder) + { + UINT32 aModelIndex = 1; + UINT32 aSymbol = 0; + RC_INIT_VAR + for(UINT32 aBitIndex = 0; aBitIndex < m_NumBitLevels; aBitIndex++) + { + // UINT32 aBit = m_Models[aModelIndex].Decode(aRangeDecoder); + // aModelIndex <<= 1; + // aModelIndex += aBit; + // aSymbol |= (aBit << aBitIndex); + RC_GETBIT2(aNumMoveBits, m_Models[aModelIndex].m_Probability, aModelIndex, ; , aSymbol |= (1 << aBitIndex)) + } + RC_FLUSH_VAR + return aSymbol; + } +}; + +/* +////////////////////////// +// CBitTreeEncoder2 + +template +class CBitTreeEncoder2 +{ + NCompression::NArithmetic::CBitEncoder *m_Models; + UINT32 m_NumBitLevels; +public: + bool Create(UINT32 aNumBitLevels) + { + m_NumBitLevels = aNumBitLevels; + m_Models = new NCompression::NArithmetic::CBitEncoder[1 << aNumBitLevels]; + return (m_Models != 0); + } + void Init() + { + UINT32 aNumModels = 1 << m_NumBitLevels; + for(UINT32 i = 1; i < aNumModels; i++) + m_Models[i].Init(); + } + void Encode(CMyRangeEncoder *aRangeEncoder, UINT32 aSymbol) + { + UINT32 aModelIndex = 1; + for (UINT32 aBitIndex = m_NumBitLevels; aBitIndex > 0 ;) + { + aBitIndex--; + UINT32 aBit = (aSymbol >> aBitIndex ) & 1; + m_Models[aModelIndex].Encode(aRangeEncoder, aBit); + aModelIndex = (aModelIndex << 1) | aBit; + } + } + UINT32 GetPrice(UINT32 aSymbol) const + { + UINT32 aPrice = 0; + UINT32 aModelIndex = 1; + for (UINT32 aBitIndex = m_NumBitLevels; aBitIndex > 0 ;) + { + aBitIndex--; + UINT32 aBit = (aSymbol >> aBitIndex ) & 1; + aPrice += m_Models[aModelIndex].GetPrice(aBit); + aModelIndex = (aModelIndex << 1) + aBit; + } + return aPrice; + } +}; + + +////////////////////////// +// CBitTreeDecoder2 + +template +class CBitTreeDecoder2 +{ + NCompression::NArithmetic::CBitDecoder *m_Models; + UINT32 m_NumBitLevels; +public: + bool Create(UINT32 aNumBitLevels) + { + m_NumBitLevels = aNumBitLevels; + m_Models = new NCompression::NArithmetic::CBitDecoder[1 << aNumBitLevels]; + return (m_Models != 0); + } + void Init() + { + UINT32 aNumModels = 1 << m_NumBitLevels; + for(UINT32 i = 1; i < aNumModels; i++) + m_Models[i].Init(); + } + UINT32 Decode(CMyRangeDecoder *aRangeDecoder) + { + UINT32 aModelIndex = 1; + RC_INIT_VAR + for(UINT32 aBitIndex = m_NumBitLevels; aBitIndex > 0; aBitIndex--) + { + // aModelIndex = (aModelIndex << 1) + m_Models[aModelIndex].Decode(aRangeDecoder); + RC_GETBIT(aNumMoveBits, m_Models[aModelIndex].m_Probability, aModelIndex) + } + RC_FLUSH_VAR + return aModelIndex - (1 << m_NumBitLevels); + } +}; +*/ + + +#endif diff --git a/hostTools/lzma/compress/CRC.h b/hostTools/lzma/compress/CRC.h new file mode 100644 index 0000000..cbef4b6 --- /dev/null +++ b/hostTools/lzma/compress/CRC.h @@ -0,0 +1,27 @@ +#ifndef __COMMON_CRC_H +#define __COMMON_CRC_H + +#include "Portable.h" + +class CCRC +{ + UINT32 m_Value; +public: + static UINT32 m_Table[256]; + CCRC(): m_Value(0xFFFFFFFF){}; + void Init() { m_Value = 0xFFFFFFFF; } + void Update(const void *aData, UINT32 aSize); + UINT32 GetDigest() const { return m_Value ^ 0xFFFFFFFF; } + static UINT32 CalculateDigest(const void *aData, UINT32 aSize) + { + CCRC aCRC; + aCRC.Update(aData, aSize); + return aCRC.GetDigest(); + } + static bool VerifyDigest(UINT32 aDigest, const void *aData, UINT32 aSize) + { + return (CalculateDigest(aData, aSize) == aDigest); + } +}; + +#endif diff --git a/hostTools/lzma/compress/Const.h b/hostTools/lzma/compress/Const.h new file mode 100644 index 0000000..7cb9d79 --- /dev/null +++ b/hostTools/lzma/compress/Const.h @@ -0,0 +1,92 @@ +#ifndef __DEFLATE_CONST_H +#define __DEFLATE_CONST_H + +namespace NDeflate { + +const UINT32 kDistTableSize = 30; +const UINT32 kHistorySize = 0x8000; +const UINT32 kNumLenCombinations = 256; + +const UINT32 kNumHuffmanBits = 15; + +const UINT32 kLenTableSize = 29; + +const UINT32 kStaticDistTableSize = 32; +const UINT32 kStaticLenTableSize = 31; + +const UINT32 kReadTableNumber = 0x100; +const UINT32 kMatchNumber = kReadTableNumber + 1; + +const UINT32 kMainTableSize = kMatchNumber + kLenTableSize; //298; +const UINT32 kStaticMainTableSize = kMatchNumber + kStaticLenTableSize; //298; + +const UINT32 kDistTableStart = kMainTableSize; + +const UINT32 kHeapTablesSizesSum = kMainTableSize + kDistTableSize; + +const UINT32 kLevelTableSize = 19; + +const UINT32 kMaxTableSize = kHeapTablesSizesSum; // test it +const UINT32 kStaticMaxTableSize = kStaticMainTableSize + kStaticDistTableSize; + +const UINT32 kTableDirectLevels = 16; +const UINT32 kTableLevelRepNumber = kTableDirectLevels; +const UINT32 kTableLevel0Number = kTableLevelRepNumber + 1; +const UINT32 kTableLevel0Number2 = kTableLevel0Number + 1; + +const UINT32 kLevelMask = 0xF; + +const BYTE kLenStart[kLenTableSize] = {0,1,2,3,4,5,6,7,8,10,12,14,16,20,24,28,32,40,48,56,64,80,96,112,128,160,192,224, 255}; +const BYTE kLenDirectBits[kLenTableSize] = {0,0,0,0,0,0,0,0,1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0}; + + +const UINT32 kDistStart[kDistTableSize] = {0,1,2,3,4,6,8,12,16,24,32,48,64,96,128,192,256,384,512,768,1024,1536,2048,3072,4096,6144,8192,12288,16384,24576}; +const BYTE kDistDirectBits[kDistTableSize] = {0,0,0,0,1,1,2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13}; + +const BYTE kLevelDirectBits[kLevelTableSize] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7}; + +const BYTE kCodeLengthAlphabetOrder[kLevelTableSize] = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; + +const UINT32 kMatchMinLen = 3; +const UINT32 kMatchMaxLen = kNumLenCombinations + kMatchMinLen - 1; // 255 + 2; test it + +const int kFinalBlockFieldSize = 1; + +namespace NFinalBlockField +{ +enum +{ + kNotFinalBlock = 0, + kFinalBlock = 1 +}; +} + +const int kBlockTypeFieldSize = 2; + +namespace NBlockType +{ + enum + { + kStored = 0, + kFixedHuffman = 1, + kDynamicHuffman = 2, + kReserved = 3 + }; +} + +const UINT32 kDeflateNumberOfLengthCodesFieldSize = 5; +const UINT32 kDeflateNumberOfDistanceCodesFieldSize = 5; +const UINT32 kDeflateNumberOfLevelCodesFieldSize = 4; + +const UINT32 kDeflateNumberOfLitLenCodesMin = 257; + +const UINT32 kDeflateNumberOfDistanceCodesMin = 1; +const UINT32 kDeflateNumberOfLevelCodesMin = 4; + +const UINT32 kDeflateLevelCodeFieldSize = 3; + +const UINT32 kDeflateStoredBlockLengthFieldSizeSize = 16; + +} + +#endif diff --git a/hostTools/lzma/compress/IInOutStreams.cpp b/hostTools/lzma/compress/IInOutStreams.cpp new file mode 100644 index 0000000..73bd1e0 --- /dev/null +++ b/hostTools/lzma/compress/IInOutStreams.cpp @@ -0,0 +1,25 @@ +#include "Portable.h" +#include "IInOutStreams.h" + +HRESULT ISequentialInStream::Read(void *aData, UINT32 aSize, UINT32* aProcessedSize) { + if (aSize > size) + aSize = size; + *aProcessedSize = aSize; + memcpy(aData, data, aSize); + size -= aSize; + data += aSize; + return S_OK; +} + +HRESULT ISequentialOutStream::Write(const void *aData, UINT32 aSize, UINT32* aProcessedSize) { + if (aSize > size) { + overflow = true; + aSize = size; + } + *aProcessedSize = aSize; + memcpy(data, aData, aSize); + size -= aSize; + data += aSize; + total += aSize; + return S_OK; +} diff --git a/hostTools/lzma/compress/IInOutStreams.h b/hostTools/lzma/compress/IInOutStreams.h new file mode 100644 index 0000000..c084217 --- /dev/null +++ b/hostTools/lzma/compress/IInOutStreams.h @@ -0,0 +1,31 @@ +#ifndef __IINOUTSTREAMS_H +#define __IINOUTSTREAMS_H + +#include "Portable.h" + +class ISequentialInStream +{ + const char* data; + unsigned size; +public: + ISequentialInStream(const char* Adata, unsigned Asize) : data(Adata), size(Asize) { } + + HRESULT Read(void *aData, UINT32 aSize, UINT32 *aProcessedSize); +}; + +class ISequentialOutStream +{ + char* data; + unsigned size; + bool overflow; + unsigned total; +public: + ISequentialOutStream(char* Adata, unsigned Asize) : data(Adata), size(Asize), overflow(false), total(0) { } + + bool overflow_get() const { return overflow; } + unsigned size_get() const { return total; } + + HRESULT Write(const void *aData, UINT32 aSize, UINT32 *aProcessedSize); +}; + +#endif diff --git a/hostTools/lzma/compress/InByte.cpp b/hostTools/lzma/compress/InByte.cpp new file mode 100644 index 0000000..03f6a62 --- /dev/null +++ b/hostTools/lzma/compress/InByte.cpp @@ -0,0 +1,41 @@ +#include "InByte.h" + +namespace NStream{ + +CInByte::CInByte(UINT32 aBufferSize): + m_BufferSize(aBufferSize), + m_BufferBase(0) +{ + m_BufferBase = new BYTE[m_BufferSize]; +} + +CInByte::~CInByte() +{ + delete []m_BufferBase; +} + +void CInByte::Init(ISequentialInStream *aStream) +{ + m_Stream = aStream; + m_ProcessedSize = 0; + m_Buffer = m_BufferBase; + m_BufferLimit = m_Buffer; + m_StreamWasExhausted = false; +} + +bool CInByte::ReadBlock() +{ + if (m_StreamWasExhausted) + return false; + m_ProcessedSize += (m_Buffer - m_BufferBase); + UINT32 aNumProcessedBytes; + HRESULT aResult = m_Stream->Read(m_BufferBase, m_BufferSize, &aNumProcessedBytes); + if (aResult != S_OK) + throw aResult; + m_Buffer = m_BufferBase; + m_BufferLimit = m_Buffer + aNumProcessedBytes; + m_StreamWasExhausted = (aNumProcessedBytes == 0); + return (!m_StreamWasExhausted); +} + +} diff --git a/hostTools/lzma/compress/InByte.h b/hostTools/lzma/compress/InByte.h new file mode 100644 index 0000000..49bf2f3 --- /dev/null +++ b/hostTools/lzma/compress/InByte.h @@ -0,0 +1,58 @@ +#ifndef __STREAM_INBYTE_H +#define __STREAM_INBYTE_H + +#include "IInOutStreams.h" + +namespace NStream { + +class CInByte +{ + UINT64 m_ProcessedSize; + BYTE *m_BufferBase; + UINT32 m_BufferSize; + BYTE *m_Buffer; + BYTE *m_BufferLimit; + ISequentialInStream* m_Stream; + bool m_StreamWasExhausted; + + bool ReadBlock(); + +public: + CInByte(UINT32 aBufferSize = 0x100000); + ~CInByte(); + + void Init(ISequentialInStream *aStream); + + bool ReadByte(BYTE &aByte) + { + if(m_Buffer >= m_BufferLimit) + if(!ReadBlock()) + return false; + aByte = *m_Buffer++; + return true; + } + BYTE ReadByte() + { + if(m_Buffer >= m_BufferLimit) + if(!ReadBlock()) + return 0x0; + return *m_Buffer++; + } + void ReadBytes(void *aData, UINT32 aSize, UINT32 &aProcessedSize) + { + for(aProcessedSize = 0; aProcessedSize < aSize; aProcessedSize++) + if (!ReadByte(((BYTE *)aData)[aProcessedSize])) + return; + } + bool ReadBytes(void *aData, UINT32 aSize) + { + UINT32 aProcessedSize; + ReadBytes(aData, aSize, aProcessedSize); + return (aProcessedSize == aSize); + } + UINT64 GetProcessedSize() const { return m_ProcessedSize + (m_Buffer - m_BufferBase); } +}; + +} + +#endif diff --git a/hostTools/lzma/compress/LZMA.cpp b/hostTools/lzma/compress/LZMA.cpp new file mode 100644 index 0000000..3774853 --- /dev/null +++ b/hostTools/lzma/compress/LZMA.cpp @@ -0,0 +1,23 @@ +#include "LZMA.h" + +namespace NCompress { +namespace NLZMA { + +UINT32 kDistStart[kDistTableSizeMax]; + +static class CConstInit +{ +public: + CConstInit() + { + UINT32 aStartValue = 0; + int i; + for (i = 0; i < kDistTableSizeMax; i++) + { + kDistStart[i] = aStartValue; + aStartValue += (1 << kDistDirectBits[i]); + } + } +} g_ConstInit; + +}} diff --git a/hostTools/lzma/compress/LZMA.h b/hostTools/lzma/compress/LZMA.h new file mode 100644 index 0000000..1a947f7 --- /dev/null +++ b/hostTools/lzma/compress/LZMA.h @@ -0,0 +1,105 @@ +#include "LenCoder.h" + +#ifndef __LZMA_H +#define __LZMA_H + +namespace NCompress { +namespace NLZMA { + +const UINT32 kNumRepDistances = 4; + +const BYTE kNumStates = 12; + +const BYTE kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5}; +const BYTE kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10}; +const BYTE kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11}; +const BYTE kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11}; + +class CState +{ +public: + BYTE m_Index; + void Init() + { m_Index = 0; } + void UpdateChar() + { m_Index = kLiteralNextStates[m_Index]; } + void UpdateMatch() + { m_Index = kMatchNextStates[m_Index]; } + void UpdateRep() + { m_Index = kRepNextStates[m_Index]; } + void UpdateShortRep() + { m_Index = kShortRepNextStates[m_Index]; } +}; + +class CBaseCoder +{ +protected: + CState m_State; + BYTE m_PreviousByte; + bool m_PeviousIsMatch; + UINT32 m_RepDistances[kNumRepDistances]; + void Init() + { + m_State.Init(); + m_PreviousByte = 0; + m_PeviousIsMatch = false; + for(int i = 0 ; i < kNumRepDistances; i++) + m_RepDistances[i] = 0; + } +}; + +const int kNumPosSlotBits = 6; +const int kDicLogSizeMax = 28; +const int kDistTableSizeMax = kDicLogSizeMax * 2; + +extern UINT32 kDistStart[kDistTableSizeMax]; +const BYTE kDistDirectBits[kDistTableSizeMax] = +{ + 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, + 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, + 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26 +}; + +const UINT32 kNumLenToPosStates = 4; +inline UINT32 GetLenToPosState(UINT32 aLen) +{ + aLen -= 2; + if (aLen < kNumLenToPosStates) + return aLen; + return kNumLenToPosStates - 1; +} + +const int kMatchMinLen = 2; + +const int kMatchMaxLen = kMatchMinLen + NLength::kNumSymbolsTotal - 1; + +const int kNumAlignBits = 4; +const int kAlignTableSize = 1 << kNumAlignBits; +const UINT32 kAlignMask = (kAlignTableSize - 1); + +const int kStartPosModelIndex = 4; +const int kEndPosModelIndex = 14; +const int kNumPosModels = kEndPosModelIndex - kStartPosModelIndex; + +const int kNumFullDistances = 1 << (kEndPosModelIndex / 2); + + +const int kMainChoiceLiteralIndex = 0; +const int kMainChoiceMatchIndex = 1; + +const int kMatchChoiceDistanceIndex= 0; +const int kMatchChoiceRepetitionIndex = 1; + +const int kNumMoveBitsForMainChoice = 5; +const int kNumMoveBitsForPosCoders = 5; + +const int kNumMoveBitsForAlignCoders = 5; + +const int kNumMoveBitsForPosSlotCoder = 5; + +const int kNumLitPosStatesBitsEncodingMax = 4; +const int kNumLitContextBitsMax = 8; + +}} + +#endif diff --git a/hostTools/lzma/compress/LZMADecoder.cpp b/hostTools/lzma/compress/LZMADecoder.cpp new file mode 100644 index 0000000..1c834a4 --- /dev/null +++ b/hostTools/lzma/compress/LZMADecoder.cpp @@ -0,0 +1,276 @@ +#include "Portable.h" +#include "LZMADecoder.h" + +#define RETURN_E_OUTOFMEMORY_IF_FALSE(x) { if (!(x)) return E_OUTOFMEMORY; } + +namespace NCompress { +namespace NLZMA { + +HRESULT CDecoder::SetDictionarySize(UINT32 aDictionarySize) +{ + if (aDictionarySize > (1 << kDicLogSizeMax)) + return E_INVALIDARG; + + UINT32 aWindowReservSize = MyMax(aDictionarySize, UINT32(1 << 21)); + + if (m_DictionarySize != aDictionarySize) + { + m_OutWindowStream.Create(aDictionarySize, kMatchMaxLen, aWindowReservSize); + m_DictionarySize = aDictionarySize; + } + return S_OK; +} + +HRESULT CDecoder::SetLiteralProperties( + UINT32 aLiteralPosStateBits, UINT32 aLiteralContextBits) +{ + if (aLiteralPosStateBits > 8) + return E_INVALIDARG; + if (aLiteralContextBits > 8) + return E_INVALIDARG; + m_LiteralDecoder.Create(aLiteralPosStateBits, aLiteralContextBits); + return S_OK; +} + +HRESULT CDecoder::SetPosBitsProperties(UINT32 aNumPosStateBits) +{ + if (aNumPosStateBits > NLength::kNumPosStatesBitsMax) + return E_INVALIDARG; + UINT32 aNumPosStates = 1 << aNumPosStateBits; + m_LenDecoder.Create(aNumPosStates); + m_RepMatchLenDecoder.Create(aNumPosStates); + m_PosStateMask = aNumPosStates - 1; + return S_OK; +} + +CDecoder::CDecoder(): + m_DictionarySize((UINT32)-1) +{ + Create(); +} + +HRESULT CDecoder::Create() +{ + for(int i = 0; i < kNumPosModels; i++) + { + RETURN_E_OUTOFMEMORY_IF_FALSE( + m_PosDecoders[i].Create(kDistDirectBits[kStartPosModelIndex + i])); + } + return S_OK; +} + + +HRESULT CDecoder::Init(ISequentialInStream *anInStream, + ISequentialOutStream *anOutStream) +{ + m_RangeDecoder.Init(anInStream); + + m_OutWindowStream.Init(anOutStream); + + int i; + for(i = 0; i < kNumStates; i++) + { + for (UINT32 j = 0; j <= m_PosStateMask; j++) + { + m_MainChoiceDecoders[i][j].Init(); + m_MatchRepShortChoiceDecoders[i][j].Init(); + } + m_MatchChoiceDecoders[i].Init(); + m_MatchRepChoiceDecoders[i].Init(); + m_MatchRep1ChoiceDecoders[i].Init(); + m_MatchRep2ChoiceDecoders[i].Init(); + } + + m_LiteralDecoder.Init(); + + // m_RepMatchLenDecoder.Init(); + + for (i = 0; i < kNumLenToPosStates; i++) + m_PosSlotDecoder[i].Init(); + + for(i = 0; i < kNumPosModels; i++) + m_PosDecoders[i].Init(); + + m_LenDecoder.Init(); + m_RepMatchLenDecoder.Init(); + + m_PosAlignDecoder.Init(); + return S_OK; + +} + +HRESULT CDecoder::CodeReal(ISequentialInStream *anInStream, + ISequentialOutStream *anOutStream, + const UINT64 *anInSize, const UINT64 *anOutSize) +{ + if (anOutSize == NULL) + return E_INVALIDARG; + + Init(anInStream, anOutStream); + + CState aState; + aState.Init(); + bool aPeviousIsMatch = false; + BYTE aPreviousByte = 0; + UINT32 aRepDistances[kNumRepDistances]; + for(int i = 0 ; i < kNumRepDistances; i++) + aRepDistances[i] = 0; + + UINT64 aNowPos64 = 0; + UINT64 aSize = *anOutSize; + while(aNowPos64 < aSize) + { + UINT64 aNext = MyMin(aNowPos64 + (1 << 18), aSize); + while(aNowPos64 < aNext) + { + UINT32 aPosState = UINT32(aNowPos64) & m_PosStateMask; + if (m_MainChoiceDecoders[aState.m_Index][aPosState].Decode(&m_RangeDecoder) == kMainChoiceLiteralIndex) + { + // aCounts[0]++; + aState.UpdateChar(); + if(aPeviousIsMatch) + { + BYTE aMatchByte = m_OutWindowStream.GetOneByte(0 - aRepDistances[0] - 1); + aPreviousByte = m_LiteralDecoder.DecodeWithMatchByte(&m_RangeDecoder, + UINT32(aNowPos64), aPreviousByte, aMatchByte); + aPeviousIsMatch = false; + } + else + aPreviousByte = m_LiteralDecoder.DecodeNormal(&m_RangeDecoder, + UINT32(aNowPos64), aPreviousByte); + m_OutWindowStream.PutOneByte(aPreviousByte); + aNowPos64++; + } + else + { + aPeviousIsMatch = true; + UINT32 aDistance, aLen; + if(m_MatchChoiceDecoders[aState.m_Index].Decode(&m_RangeDecoder) == + kMatchChoiceRepetitionIndex) + { + if(m_MatchRepChoiceDecoders[aState.m_Index].Decode(&m_RangeDecoder) == 0) + { + if(m_MatchRepShortChoiceDecoders[aState.m_Index][aPosState].Decode(&m_RangeDecoder) == 0) + { + aState.UpdateShortRep(); + aPreviousByte = m_OutWindowStream.GetOneByte(0 - aRepDistances[0] - 1); + m_OutWindowStream.PutOneByte(aPreviousByte); + aNowPos64++; + // aCounts[3 + 4]++; + continue; + } + // aCounts[3 + 0]++; + aDistance = aRepDistances[0]; + } + else + { + if(m_MatchRep1ChoiceDecoders[aState.m_Index].Decode(&m_RangeDecoder) == 0) + { + aDistance = aRepDistances[1]; + aRepDistances[1] = aRepDistances[0]; + // aCounts[3 + 1]++; + } + else + { + if (m_MatchRep2ChoiceDecoders[aState.m_Index].Decode(&m_RangeDecoder) == 0) + { + // aCounts[3 + 2]++; + aDistance = aRepDistances[2]; + } + else + { + // aCounts[3 + 3]++; + aDistance = aRepDistances[3]; + aRepDistances[3] = aRepDistances[2]; + } + aRepDistances[2] = aRepDistances[1]; + aRepDistances[1] = aRepDistances[0]; + } + aRepDistances[0] = aDistance; + } + aLen = m_RepMatchLenDecoder.Decode(&m_RangeDecoder, aPosState) + kMatchMinLen; + // aCounts[aLen]++; + aState.UpdateRep(); + } + else + { + aLen = kMatchMinLen + m_LenDecoder.Decode(&m_RangeDecoder, aPosState); + aState.UpdateMatch(); + UINT32 aPosSlot = m_PosSlotDecoder[GetLenToPosState(aLen)].Decode(&m_RangeDecoder); + // aCounts[aPosSlot]++; + if (aPosSlot >= kStartPosModelIndex) + { + aDistance = kDistStart[aPosSlot]; + if (aPosSlot < kEndPosModelIndex) + aDistance += m_PosDecoders[aPosSlot - kStartPosModelIndex].Decode(&m_RangeDecoder); + else + { + aDistance += (m_RangeDecoder.DecodeDirectBits(kDistDirectBits[aPosSlot] - + kNumAlignBits) << kNumAlignBits); + aDistance += m_PosAlignDecoder.Decode(&m_RangeDecoder); + } + } + else + aDistance = aPosSlot; + + + aRepDistances[3] = aRepDistances[2]; + aRepDistances[2] = aRepDistances[1]; + aRepDistances[1] = aRepDistances[0]; + + aRepDistances[0] = aDistance; + // UpdateStat(aLen, aPosSlot); + } + if (aDistance >= aNowPos64) + throw E_INVALIDDATA; + m_OutWindowStream.CopyBackBlock(aDistance, aLen); + aNowPos64 += aLen; + aPreviousByte = m_OutWindowStream.GetOneByte(0 - 1); + } + } + } + return Flush(); +} + +HRESULT CDecoder::Code(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream, const UINT64 *anInSize, const UINT64 *anOutSize) +{ + try { + return CodeReal(anInStream, anOutStream, anInSize, anOutSize); + } catch (HRESULT& e) { + return e; + } catch (...) { + return E_FAIL; + } +} + +HRESULT CDecoder::ReadCoderProperties(ISequentialInStream *anInStream) +{ + UINT32 aNumPosStateBits; + UINT32 aLiteralPosStateBits; + UINT32 aLiteralContextBits; + UINT32 aDictionarySize; + + UINT32 aProcessesedSize; + + BYTE aByte; + RETURN_IF_NOT_S_OK(anInStream->Read(&aByte, sizeof(aByte), &aProcessesedSize)); + if (aProcessesedSize != sizeof(aByte)) + return E_INVALIDARG; + + aLiteralContextBits = aByte % 9; + BYTE aRemainder = aByte / 9; + aLiteralPosStateBits = aRemainder % 5; + aNumPosStateBits = aRemainder / 5; + + RETURN_IF_NOT_S_OK(anInStream->Read(&aDictionarySize, sizeof(aDictionarySize), &aProcessesedSize)); + if (aProcessesedSize != sizeof(aDictionarySize)) + return E_INVALIDARG; + + RETURN_IF_NOT_S_OK(SetDictionarySize(aDictionarySize)); + RETURN_IF_NOT_S_OK(SetLiteralProperties(aLiteralPosStateBits, aLiteralContextBits)); + RETURN_IF_NOT_S_OK(SetPosBitsProperties(aNumPosStateBits)); + + return S_OK; +} + +}} diff --git a/hostTools/lzma/compress/LZMADecoder.h b/hostTools/lzma/compress/LZMADecoder.h new file mode 100644 index 0000000..610a84d --- /dev/null +++ b/hostTools/lzma/compress/LZMADecoder.h @@ -0,0 +1,64 @@ +#ifndef __LZARITHMETIC_DECODER_H +#define __LZARITHMETIC_DECODER_H + +#include "WindowOut.h" +#include "LZMA.h" +#include "LenCoder.h" +#include "LiteralCoder.h" + +namespace NCompress { +namespace NLZMA { + +typedef CMyBitDecoder CMyBitDecoder2; + +class CDecoder +{ + NStream::NWindow::COut m_OutWindowStream; + CMyRangeDecoder m_RangeDecoder; + + CMyBitDecoder2 m_MainChoiceDecoders[kNumStates][NLength::kNumPosStatesMax]; + CMyBitDecoder2 m_MatchChoiceDecoders[kNumStates]; + CMyBitDecoder2 m_MatchRepChoiceDecoders[kNumStates]; + CMyBitDecoder2 m_MatchRep1ChoiceDecoders[kNumStates]; + CMyBitDecoder2 m_MatchRep2ChoiceDecoders[kNumStates]; + CMyBitDecoder2 m_MatchRepShortChoiceDecoders[kNumStates][NLength::kNumPosStatesMax]; + + CBitTreeDecoder m_PosSlotDecoder[kNumLenToPosStates]; + + CReverseBitTreeDecoder2 m_PosDecoders[kNumPosModels]; + CReverseBitTreeDecoder m_PosAlignDecoder; + // CBitTreeDecoder2 m_PosDecoders[kNumPosModels]; + // CBitTreeDecoder m_PosAlignDecoder; + + NLength::CDecoder m_LenDecoder; + NLength::CDecoder m_RepMatchLenDecoder; + + NLiteral::CDecoder m_LiteralDecoder; + + UINT32 m_DictionarySize; + + UINT32 m_PosStateMask; + + HRESULT Create(); + + HRESULT Init(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream); + + HRESULT Flush() { return m_OutWindowStream.Flush(); } + + HRESULT CodeReal(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream, const UINT64 *anInSize, const UINT64 *anOutSize); + +public: + + CDecoder(); + + HRESULT Code(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream, const UINT64 *anInSize, const UINT64 *anOutSize); + HRESULT ReadCoderProperties(ISequentialInStream *anInStream); + + HRESULT SetDictionarySize(UINT32 aDictionarySize); + HRESULT SetLiteralProperties(UINT32 aLiteralPosStateBits, UINT32 aLiteralContextBits); + HRESULT SetPosBitsProperties(UINT32 aNumPosStateBits); +}; + +}} + +#endif diff --git a/hostTools/lzma/compress/LZMAEncoder.cpp b/hostTools/lzma/compress/LZMAEncoder.cpp new file mode 100644 index 0000000..9b30834 --- /dev/null +++ b/hostTools/lzma/compress/LZMAEncoder.cpp @@ -0,0 +1,981 @@ +#include "Portable.h" +#include "LZMAEncoder.h" + +#include "BinTree2Main.h" + +using namespace NCompression; +using namespace NArithmetic; + +#define RETURN_E_OUTOFMEMORY_IF_FALSE(x) { if (!(x)) return E_OUTOFMEMORY; } + +namespace NCompress { +namespace NLZMA { + +BYTE g_FastPos[1024]; + +class CFastPosInit +{ +public: + CFastPosInit() + { + int c = 0; + const int kFastSlots = 20; + c = 0; + for (BYTE aSlotFast = 0; aSlotFast < kFastSlots; aSlotFast++) + { + UINT32 k = (1 << kDistDirectBits[aSlotFast]); + for (UINT32 j = 0; j < k; j++, c++) + g_FastPos[c] = aSlotFast; + } + } +} g_FastPosInit; + +const int kDefaultDictionaryLogSize = 20; +const int kNumFastBytesDefault = 0x20; + +CEncoder::CEncoder(): + m_DictionarySize(1 << kDefaultDictionaryLogSize), + m_DictionarySizePrev(UINT32(-1)), + m_NumFastBytes(kNumFastBytesDefault), + m_NumFastBytesPrev(UINT32(-1)), + m_DistTableSize(kDefaultDictionaryLogSize * 2), + m_PosStateBits(2), + m_PosStateMask(4 - 1), + m_LiteralPosStateBits(0), + m_LiteralContextBits(3) +{ + m_MaxMode = false; + m_FastMode = false; + m_PosAlignEncoder.Create(kNumAlignBits); + for(int i = 0; i < kNumPosModels; i++) + m_PosEncoders[i].Create(kDistDirectBits[kStartPosModelIndex + i]); +} + +HRESULT CEncoder::Create() +{ + if (m_DictionarySize == m_DictionarySizePrev && m_NumFastBytesPrev == m_NumFastBytes) + return S_OK; + RETURN_IF_NOT_S_OK(m_MatchFinder.Create(m_DictionarySize, kNumOpts, m_NumFastBytes, + kMatchMaxLen - m_NumFastBytes)); + m_DictionarySizePrev = m_DictionarySize; + m_NumFastBytesPrev = m_NumFastBytes; + m_LiteralEncoder.Create(m_LiteralPosStateBits, m_LiteralContextBits); + m_LenEncoder.Create(1 << m_PosStateBits); + m_RepMatchLenEncoder.Create(1 << m_PosStateBits); + return S_OK; +} + +HRESULT CEncoder::SetEncoderAlgorithm(UINT32 A) { + UINT32 aMaximize = A; + if (aMaximize > 2) + return E_INVALIDARG; + + m_FastMode = (aMaximize == 0); + m_MaxMode = (aMaximize >= 2); + + return S_OK; +} + +HRESULT CEncoder::SetEncoderNumFastBytes(UINT32 A) { + UINT32 aNumFastBytes = A; + if(aNumFastBytes < 2 || aNumFastBytes > kMatchMaxLen) + return E_INVALIDARG; + + m_NumFastBytes = aNumFastBytes; + + return S_OK; +} + +HRESULT CEncoder::SetDictionarySize(UINT32 aDictionarySize) +{ + if (aDictionarySize > UINT32(1 << kDicLogSizeMax)) + return E_INVALIDARG; + m_DictionarySize = aDictionarySize; + UINT32 aDicLogSize; + for(aDicLogSize = 0; aDicLogSize < kDicLogSizeMax; aDicLogSize++) + if (aDictionarySize <= (UINT32(1) << aDicLogSize)) + break; + m_DistTableSize = aDicLogSize * 2; + return S_OK; +} + +HRESULT CEncoder::SetLiteralProperties(UINT32 aLiteralPosStateBits, UINT32 aLiteralContextBits) +{ + if (aLiteralPosStateBits > kNumLitPosStatesBitsEncodingMax) + return E_INVALIDARG; + if (aLiteralContextBits > kNumLitContextBitsMax) + return E_INVALIDARG; + m_LiteralPosStateBits = aLiteralPosStateBits; + m_LiteralContextBits = aLiteralContextBits; + return S_OK; +} + +HRESULT CEncoder::SetPosBitsProperties(UINT32 aNumPosStateBits) +{ + if (aNumPosStateBits > NLength::kNumPosStatesBitsEncodingMax) + return E_INVALIDARG; + m_PosStateBits = aNumPosStateBits; + m_PosStateMask = (1 << m_PosStateBits) - 1; + return S_OK; +} + + +HRESULT CEncoder::WriteCoderProperties(ISequentialOutStream *anOutStream) +{ + BYTE aByte = (m_PosStateBits * 5 + m_LiteralPosStateBits) * 9 + m_LiteralContextBits; + UINT32 aProcessedSize; + HRESULT aResult = anOutStream->Write(&aByte, sizeof(aByte), &aProcessedSize); + if (aResult != S_OK) + return aResult; + if (aProcessedSize != sizeof(aByte)) + return E_FAIL; + aResult = anOutStream->Write(&m_DictionarySize, sizeof(m_DictionarySize), &aProcessedSize); + if (aResult != S_OK) + return aResult; + if (aProcessedSize != sizeof(m_DictionarySize)) + return E_FAIL; + return S_OK; +} + +HRESULT CEncoder::Init(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream) +{ + CBaseCoder::Init(); + + RETURN_IF_NOT_S_OK(m_MatchFinder.Init(anInStream)); + m_RangeEncoder.Init(anOutStream); + + int i; + for(i = 0; i < kNumStates; i++) + { + for (UINT32 j = 0; j <= m_PosStateMask; j++) + { + m_MainChoiceEncoders[i][j].Init(); + m_MatchRepShortChoiceEncoders[i][j].Init(); + } + m_MatchChoiceEncoders[i].Init(); + m_MatchRepChoiceEncoders[i].Init(); + m_MatchRep1ChoiceEncoders[i].Init(); + m_MatchRep2ChoiceEncoders[i].Init(); + } + + m_LiteralEncoder.Init(); + + // m_RepMatchLenEncoder.Init(); + + for(i = 0; i < kNumLenToPosStates; i++) + m_PosSlotEncoder[i].Init(); + + for(i = 0; i < kNumPosModels; i++) + m_PosEncoders[i].Init(); + + m_LenEncoder.Init(); + m_RepMatchLenEncoder.Init(); + + m_PosAlignEncoder.Init(); + + m_LongestMatchWasFound = false; + m_OptimumEndIndex = 0; + m_OptimumCurrentIndex = 0; + m_AdditionalOffset = 0; + + return S_OK; +} + +void CEncoder::MovePos(UINT32 aNum) +{ + for (;aNum > 0; aNum--) + { + m_MatchFinder.DummyLongestMatch(); + HRESULT aResult = m_MatchFinder.MovePos(); + if (aResult != S_OK) + throw aResult; + m_AdditionalOffset++; + } +} + +UINT32 CEncoder::Backward(UINT32 &aBackRes, UINT32 aCur) +{ + m_OptimumEndIndex = aCur; + UINT32 aPosMem = m_Optimum[aCur].PosPrev; + UINT32 aBackMem = m_Optimum[aCur].BackPrev; + do + { + if (m_Optimum[aCur].Prev1IsChar) + { + m_Optimum[aPosMem].MakeAsChar(); + m_Optimum[aPosMem].PosPrev = aPosMem - 1; + if (m_Optimum[aCur].Prev2) + { + m_Optimum[aPosMem - 1].Prev1IsChar = false; + m_Optimum[aPosMem - 1].PosPrev = m_Optimum[aCur].PosPrev2; + m_Optimum[aPosMem - 1].BackPrev = m_Optimum[aCur].BackPrev2; + } + } + UINT32 aPosPrev = aPosMem; + UINT32 aBackCur = aBackMem; + + aBackMem = m_Optimum[aPosPrev].BackPrev; + aPosMem = m_Optimum[aPosPrev].PosPrev; + + m_Optimum[aPosPrev].BackPrev = aBackCur; + m_Optimum[aPosPrev].PosPrev = aCur; + aCur = aPosPrev; + } + while(aCur > 0); + aBackRes = m_Optimum[0].BackPrev; + m_OptimumCurrentIndex = m_Optimum[0].PosPrev; + return m_OptimumCurrentIndex; +} + +/* +inline UINT32 GetMatchLen(const BYTE *aData, UINT32 aBack, UINT32 aLimit) +{ + aBack++; + for(UINT32 i = 0; i < aLimit && aData[i] == aData[i - aBack]; i++); + return i; +} +*/ + +UINT32 CEncoder::GetOptimum(UINT32 &aBackRes, UINT32 aPosition) +{ + if(m_OptimumEndIndex != m_OptimumCurrentIndex) + { + UINT32 aLen = m_Optimum[m_OptimumCurrentIndex].PosPrev - m_OptimumCurrentIndex; + aBackRes = m_Optimum[m_OptimumCurrentIndex].BackPrev; + m_OptimumCurrentIndex = m_Optimum[m_OptimumCurrentIndex].PosPrev; + return aLen; + } + m_OptimumCurrentIndex = 0; + m_OptimumEndIndex = 0; // test it; + + UINT32 aLenMain; + if (!m_LongestMatchWasFound) + aLenMain = ReadMatchDistances(); + else + { + aLenMain = m_LongestMatchLength; + m_LongestMatchWasFound = false; + } + + + UINT32 aReps[kNumRepDistances]; + UINT32 aRepLens[kNumRepDistances]; + UINT32 RepMaxIndex = 0; + int i; + for(i = 0; i < kNumRepDistances; i++) + { + aReps[i] = m_RepDistances[i]; + aRepLens[i] = m_MatchFinder.GetMatchLen(0 - 1, aReps[i], kMatchMaxLen); + if (i == 0 || aRepLens[i] > aRepLens[RepMaxIndex]) + RepMaxIndex = i; + } + if(aRepLens[RepMaxIndex] > m_NumFastBytes) + { + aBackRes = RepMaxIndex; + MovePos(aRepLens[RepMaxIndex] - 1); + return aRepLens[RepMaxIndex]; + } + + if(aLenMain > m_NumFastBytes) + { + UINT32 aBackMain = (aLenMain < m_NumFastBytes) ? m_MatchDistances[aLenMain] : + m_MatchDistances[m_NumFastBytes]; + aBackRes = aBackMain + kNumRepDistances; + MovePos(aLenMain - 1); + return aLenMain; + } + BYTE aCurrentByte = m_MatchFinder.GetIndexByte(0 - 1); + + m_Optimum[0].State = m_State; + + BYTE aMatchByte; + + aMatchByte = m_MatchFinder.GetIndexByte(0 - m_RepDistances[0] - 1 - 1); + + UINT32 aPosState = (aPosition & m_PosStateMask); + + m_Optimum[1].Price = m_MainChoiceEncoders[m_State.m_Index][aPosState].GetPrice(kMainChoiceLiteralIndex) + + m_LiteralEncoder.GetPrice(aPosition, m_PreviousByte, m_PeviousIsMatch, aMatchByte, aCurrentByte); + m_Optimum[1].MakeAsChar(); + + m_Optimum[1].PosPrev = 0; + + for (i = 0; i < kNumRepDistances; i++) + m_Optimum[0].Backs[i] = aReps[i]; + + UINT32 aMatchPrice = m_MainChoiceEncoders[m_State.m_Index][aPosState].GetPrice(kMainChoiceMatchIndex); + UINT32 aRepMatchPrice = aMatchPrice + + m_MatchChoiceEncoders[m_State.m_Index].GetPrice(kMatchChoiceRepetitionIndex); + + if(aMatchByte == aCurrentByte) + { + UINT32 aShortRepPrice = aRepMatchPrice + GetRepLen1Price(m_State, aPosState); + if(aShortRepPrice < m_Optimum[1].Price) + { + m_Optimum[1].Price = aShortRepPrice; + m_Optimum[1].MakeAsShortRep(); + } + } + if(aLenMain < 2) + { + aBackRes = m_Optimum[1].BackPrev; + return 1; + } + + + UINT32 aNormalMatchPrice = aMatchPrice + + m_MatchChoiceEncoders[m_State.m_Index].GetPrice(kMatchChoiceDistanceIndex); + + if (aLenMain <= aRepLens[RepMaxIndex]) + aLenMain = 0; + + UINT32 aLen; + for(aLen = 2; aLen <= aLenMain; aLen++) + { + m_Optimum[aLen].PosPrev = 0; + m_Optimum[aLen].BackPrev = m_MatchDistances[aLen] + kNumRepDistances; + m_Optimum[aLen].Price = aNormalMatchPrice + + GetPosLenPrice(m_MatchDistances[aLen], aLen, aPosState); + m_Optimum[aLen].Prev1IsChar = false; + } + + if (aLenMain < aRepLens[RepMaxIndex]) + aLenMain = aRepLens[RepMaxIndex]; + + for (; aLen <= aLenMain; aLen++) + m_Optimum[aLen].Price = kIfinityPrice; + + for(i = 0; i < kNumRepDistances; i++) + { + unsigned aRepLen = aRepLens[i]; + for(UINT32 aLenTest = 2; aLenTest <= aRepLen; aLenTest++) + { + UINT32 aCurAndLenPrice = aRepMatchPrice + GetRepPrice(i, aLenTest, m_State, aPosState); + COptimal &anOptimum = m_Optimum[aLenTest]; + if (aCurAndLenPrice < anOptimum.Price) + { + anOptimum.Price = aCurAndLenPrice; + anOptimum.PosPrev = 0; + anOptimum.BackPrev = i; + anOptimum.Prev1IsChar = false; + } + } + } + + UINT32 aCur = 0; + UINT32 aLenEnd = aLenMain; + + while(true) + { + aCur++; + if(aCur == aLenEnd) + return Backward(aBackRes, aCur); + aPosition++; + UINT32 aPosPrev = m_Optimum[aCur].PosPrev; + CState aState; + if (m_Optimum[aCur].Prev1IsChar) + { + aPosPrev--; + if (m_Optimum[aCur].Prev2) + { + aState = m_Optimum[m_Optimum[aCur].PosPrev2].State; + if (m_Optimum[aCur].BackPrev2 < kNumRepDistances) + aState.UpdateRep(); + else + aState.UpdateMatch(); + } + else + aState = m_Optimum[aPosPrev].State; + aState.UpdateChar(); + } + else + aState = m_Optimum[aPosPrev].State; + bool aPrevWasMatch; + if (aPosPrev == aCur - 1) + { + if (m_Optimum[aCur].IsShortRep()) + { + aPrevWasMatch = true; + aState.UpdateShortRep(); + } + else + { + aPrevWasMatch = false; + aState.UpdateChar(); + } + /* + if (m_Optimum[aCur].Prev1IsChar) + for(int i = 0; i < kNumRepDistances; i++) + aReps[i] = m_Optimum[aPosPrev].Backs[i]; + */ + } + else + { + aPrevWasMatch = true; + UINT32 aPos; + if (m_Optimum[aCur].Prev1IsChar && m_Optimum[aCur].Prev2) + { + aPosPrev = m_Optimum[aCur].PosPrev2; + aPos = m_Optimum[aCur].BackPrev2; + aState.UpdateRep(); + } + else + { + aPos = m_Optimum[aCur].BackPrev; + if (aPos < kNumRepDistances) + aState.UpdateRep(); + else + aState.UpdateMatch(); + } + if (aPos < kNumRepDistances) + { + aReps[0] = m_Optimum[aPosPrev].Backs[aPos]; + UINT32 i; + for(i = 1; i <= aPos; i++) + aReps[i] = m_Optimum[aPosPrev].Backs[i - 1]; + for(; i < kNumRepDistances; i++) + aReps[i] = m_Optimum[aPosPrev].Backs[i]; + } + else + { + aReps[0] = (aPos - kNumRepDistances); + for(UINT32 i = 1; i < kNumRepDistances; i++) + aReps[i] = m_Optimum[aPosPrev].Backs[i - 1]; + } + } + m_Optimum[aCur].State = aState; + for(UINT32 i = 0; i < kNumRepDistances; i++) + m_Optimum[aCur].Backs[i] = aReps[i]; + UINT32 aNewLen = ReadMatchDistances(); + if(aNewLen > m_NumFastBytes) + { + m_LongestMatchLength = aNewLen; + m_LongestMatchWasFound = true; + return Backward(aBackRes, aCur); + } + UINT32 aCurPrice = m_Optimum[aCur].Price; + // BYTE aCurrentByte = m_MatchFinder.GetIndexByte(0 - 1); + // BYTE aMatchByte = m_MatchFinder.GetIndexByte(0 - aReps[0] - 1 - 1); + const BYTE *aData = m_MatchFinder.GetPointerToCurrentPos() - 1; + BYTE aCurrentByte = *aData; + BYTE aMatchByte = aData[0 - aReps[0] - 1]; + + UINT32 aPosState = (aPosition & m_PosStateMask); + + UINT32 aCurAnd1Price = aCurPrice + + m_MainChoiceEncoders[aState.m_Index][aPosState].GetPrice(kMainChoiceLiteralIndex) + + m_LiteralEncoder.GetPrice(aPosition, aData[-1], aPrevWasMatch, aMatchByte, aCurrentByte); + + COptimal &aNextOptimum = m_Optimum[aCur + 1]; + + bool aNextIsChar = false; + if (aCurAnd1Price < aNextOptimum.Price) + { + aNextOptimum.Price = aCurAnd1Price; + aNextOptimum.PosPrev = aCur; + aNextOptimum.MakeAsChar(); + aNextIsChar = true; + } + + UINT32 aMatchPrice = aCurPrice + m_MainChoiceEncoders[aState.m_Index][aPosState].GetPrice(kMainChoiceMatchIndex); + UINT32 aRepMatchPrice = aMatchPrice + m_MatchChoiceEncoders[aState.m_Index].GetPrice(kMatchChoiceRepetitionIndex); + + if(aMatchByte == aCurrentByte && + !(aNextOptimum.PosPrev < aCur && aNextOptimum.BackPrev == 0)) + { + UINT32 aShortRepPrice = aRepMatchPrice + GetRepLen1Price(aState, aPosState); + if(aShortRepPrice <= aNextOptimum.Price) + { + aNextOptimum.Price = aShortRepPrice; + aNextOptimum.PosPrev = aCur; + aNextOptimum.MakeAsShortRep(); + // aNextIsChar = false; + } + } + /* + if(aNewLen == 2 && m_MatchDistances[2] >= kDistLimit2) // test it maybe set 2000 ? + continue; + */ + + UINT32 aNumAvailableBytes = m_MatchFinder.GetNumAvailableBytes() + 1; + aNumAvailableBytes = MyMin(kNumOpts - 1 - aCur, aNumAvailableBytes); + + if (aNumAvailableBytes < 2) + continue; + if (aNumAvailableBytes > m_NumFastBytes) + aNumAvailableBytes = m_NumFastBytes; + if (aNumAvailableBytes >= 3 && !aNextIsChar) + { + UINT32 aBackOffset = aReps[0] + 1; + UINT32 aTemp; + for (aTemp = 1; aTemp < aNumAvailableBytes; aTemp++) + if (aData[aTemp] != aData[aTemp - aBackOffset]) + break; + UINT32 aLenTest2 = aTemp - 1; + if (aLenTest2 >= 2) + { + CState aState2 = aState; + aState2.UpdateChar(); + UINT32 aPosStateNext = (aPosition + 1) & m_PosStateMask; + UINT32 aNextRepMatchPrice = aCurAnd1Price + + m_MainChoiceEncoders[aState2.m_Index][aPosStateNext].GetPrice(kMainChoiceMatchIndex) + + m_MatchChoiceEncoders[aState2.m_Index].GetPrice(kMatchChoiceRepetitionIndex); + // for (; aLenTest2 >= 2; aLenTest2--) + { + while(aLenEnd < aCur + 1 + aLenTest2) + m_Optimum[++aLenEnd].Price = kIfinityPrice; + UINT32 aCurAndLenPrice = aNextRepMatchPrice + GetRepPrice( + 0, aLenTest2, aState2, aPosStateNext); + COptimal &anOptimum = m_Optimum[aCur + 1 + aLenTest2]; + if (aCurAndLenPrice < anOptimum.Price) + { + anOptimum.Price = aCurAndLenPrice; + anOptimum.PosPrev = aCur + 1; + anOptimum.BackPrev = 0; + anOptimum.Prev1IsChar = true; + anOptimum.Prev2 = false; + } + } + } + } + for(UINT32 aRepIndex = 0; aRepIndex < kNumRepDistances; aRepIndex++) + { + // UINT32 aRepLen = m_MatchFinder.GetMatchLen(0 - 1, aReps[aRepIndex], aNewLen); // test it; + UINT32 aBackOffset = aReps[aRepIndex] + 1; + UINT32 aLenTest; + for (aLenTest = 0; aLenTest < aNumAvailableBytes; aLenTest++) + if (aData[aLenTest] != aData[aLenTest - aBackOffset]) + break; + for(; aLenTest >= 2; aLenTest--) + { + while(aLenEnd < aCur + aLenTest) + m_Optimum[++aLenEnd].Price = kIfinityPrice; + UINT32 aCurAndLenPrice = aRepMatchPrice + GetRepPrice(aRepIndex, aLenTest, aState, aPosState); + COptimal &anOptimum = m_Optimum[aCur + aLenTest]; + if (aCurAndLenPrice < anOptimum.Price) + { + anOptimum.Price = aCurAndLenPrice; + anOptimum.PosPrev = aCur; + anOptimum.BackPrev = aRepIndex; + anOptimum.Prev1IsChar = false; + } + + /* + if (m_MaxMode) + { + UINT32 aTemp; + for (aTemp = aLenTest + 1; aTemp < aNumAvailableBytes; aTemp++) + if (aData[aTemp] != aData[aTemp - aBackOffset]) + break; + UINT32 aLenTest2 = aTemp - (aLenTest + 1); + if (aLenTest2 >= 2) + { + CState aState2 = aState; + aState2.UpdateRep(); + UINT32 aPosStateNext = (aPosition + aLenTest) & m_PosStateMask; + UINT32 aCurAndLenCharPrice = aCurAndLenPrice + + m_MainChoiceEncoders[aState2.m_Index][aPosStateNext].GetPrice(kMainChoiceLiteralIndex) + + m_LiteralEncoder.GetPrice(aPosition + aLenTest, aData[aLenTest - 1], + true, aData[aLenTest - aBackOffset], aData[aLenTest]); + aState2.UpdateChar(); + aPosStateNext = (aPosition + aLenTest + 1) & m_PosStateMask; + UINT32 aNextMatchPrice = aCurAndLenCharPrice + m_MainChoiceEncoders[aState2.m_Index][aPosStateNext].GetPrice(kMainChoiceMatchIndex); + UINT32 aNextRepMatchPrice = aNextMatchPrice + m_MatchChoiceEncoders[aState2.m_Index].GetPrice(kMatchChoiceRepetitionIndex); + + // for(; aLenTest2 >= 2; aLenTest2--) + { + UINT32 anOffset = aLenTest + 1 + aLenTest2; + while(aLenEnd < aCur + anOffset) + m_Optimum[++aLenEnd].Price = kIfinityPrice; + UINT32 aCurAndLenPrice = aNextRepMatchPrice + GetRepPrice( + 0, aLenTest2, aState2, aPosStateNext); + COptimal &anOptimum = m_Optimum[aCur + anOffset]; + if (aCurAndLenPrice < anOptimum.Price) + { + anOptimum.Price = aCurAndLenPrice; + anOptimum.PosPrev = aCur + aLenTest + 1; + anOptimum.BackPrev = 0; + anOptimum.Prev1IsChar = true; + anOptimum.Prev2 = true; + anOptimum.PosPrev2 = aCur; + anOptimum.BackPrev2 = aRepIndex; + } + } + } + } + */ + } + } + + // for(UINT32 aLenTest = 2; aLenTest <= aNewLen; aLenTest++) + if (aNewLen > aNumAvailableBytes) + aNewLen = aNumAvailableBytes; + if (aNewLen >= 2) + { + if (aNewLen == 2 && m_MatchDistances[2] >= 0x80) + continue; + UINT32 aNormalMatchPrice = aMatchPrice + + m_MatchChoiceEncoders[aState.m_Index].GetPrice(kMatchChoiceDistanceIndex); + while(aLenEnd < aCur + aNewLen) + m_Optimum[++aLenEnd].Price = kIfinityPrice; + + for(UINT32 aLenTest = aNewLen; aLenTest >= 2; aLenTest--) + { + UINT32 aCurBack = m_MatchDistances[aLenTest]; + UINT32 aCurAndLenPrice = aNormalMatchPrice + GetPosLenPrice(aCurBack, aLenTest, aPosState); + COptimal &anOptimum = m_Optimum[aCur + aLenTest]; + if (aCurAndLenPrice < anOptimum.Price) + { + anOptimum.Price = aCurAndLenPrice; + anOptimum.PosPrev = aCur; + anOptimum.BackPrev = aCurBack + kNumRepDistances; + anOptimum.Prev1IsChar = false; + } + + if (m_MaxMode) + { + UINT32 aBackOffset = aCurBack + 1; + UINT32 aTemp; + for (aTemp = aLenTest + 1; aTemp < aNumAvailableBytes; aTemp++) + if (aData[aTemp] != aData[aTemp - aBackOffset]) + break; + UINT32 aLenTest2 = aTemp - (aLenTest + 1); + if (aLenTest2 >= 2) + { + CState aState2 = aState; + aState2.UpdateMatch(); + UINT32 aPosStateNext = (aPosition + aLenTest) & m_PosStateMask; + UINT32 aCurAndLenCharPrice = aCurAndLenPrice + + m_MainChoiceEncoders[aState2.m_Index][aPosStateNext].GetPrice(kMainChoiceLiteralIndex) + + m_LiteralEncoder.GetPrice(aPosition + aLenTest, aData[aLenTest - 1], + true, aData[aLenTest - aBackOffset], aData[aLenTest]); + aState2.UpdateChar(); + aPosStateNext = (aPosition + aLenTest + 1) & m_PosStateMask; + UINT32 aNextMatchPrice = aCurAndLenCharPrice + m_MainChoiceEncoders[aState2.m_Index][aPosStateNext].GetPrice(kMainChoiceMatchIndex); + UINT32 aNextRepMatchPrice = aNextMatchPrice + m_MatchChoiceEncoders[aState2.m_Index].GetPrice(kMatchChoiceRepetitionIndex); + + // for(; aLenTest2 >= 2; aLenTest2--) + { + UINT32 anOffset = aLenTest + 1 + aLenTest2; + while(aLenEnd < aCur + anOffset) + m_Optimum[++aLenEnd].Price = kIfinityPrice; + UINT32 aCurAndLenPrice = aNextRepMatchPrice + GetRepPrice( + 0, aLenTest2, aState2, aPosStateNext); + COptimal &anOptimum = m_Optimum[aCur + anOffset]; + if (aCurAndLenPrice < anOptimum.Price) + { + anOptimum.Price = aCurAndLenPrice; + anOptimum.PosPrev = aCur + aLenTest + 1; + anOptimum.BackPrev = 0; + anOptimum.Prev1IsChar = true; + anOptimum.Prev2 = true; + anOptimum.PosPrev2 = aCur; + anOptimum.BackPrev2 = aCurBack + kNumRepDistances; + } + } + } + } + } + } + } +} + +static bool inline ChangePair(UINT32 aSmall, UINT32 aBig) +{ + const int kDif = 7; + return (aSmall < (UINT32(1) << (32-kDif)) && aBig >= (aSmall << kDif)); +} + + +UINT32 CEncoder::GetOptimumFast(UINT32 &aBackRes, UINT32 aPosition) +{ + UINT32 aLenMain; + if (!m_LongestMatchWasFound) + aLenMain = ReadMatchDistances(); + else + { + aLenMain = m_LongestMatchLength; + m_LongestMatchWasFound = false; + } + UINT32 aRepLens[kNumRepDistances]; + UINT32 RepMaxIndex = 0; + for(int i = 0; i < kNumRepDistances; i++) + { + aRepLens[i] = m_MatchFinder.GetMatchLen(0 - 1, m_RepDistances[i], kMatchMaxLen); + if (i == 0 || aRepLens[i] > aRepLens[RepMaxIndex]) + RepMaxIndex = i; + } + if(aRepLens[RepMaxIndex] >= m_NumFastBytes) + { + aBackRes = RepMaxIndex; + MovePos(aRepLens[RepMaxIndex] - 1); + return aRepLens[RepMaxIndex]; + } + if(aLenMain >= m_NumFastBytes) + { + aBackRes = m_MatchDistances[m_NumFastBytes] + kNumRepDistances; + MovePos(aLenMain - 1); + return aLenMain; + } + while (aLenMain > 2) + { + if (!ChangePair(m_MatchDistances[aLenMain - 1], + m_MatchDistances[aLenMain])) + break; + aLenMain--; + } + if (aLenMain == 2 && m_MatchDistances[2] >= 0x80) + aLenMain = 1; + + UINT32 aBackMain = m_MatchDistances[aLenMain]; + if (aRepLens[RepMaxIndex] >= 2) + { + if (aRepLens[RepMaxIndex] + 1 >= aLenMain || + aRepLens[RepMaxIndex] + 2 >= aLenMain && (aBackMain > (1<<12))) + { + aBackRes = RepMaxIndex; + MovePos(aRepLens[RepMaxIndex] - 1); + return aRepLens[RepMaxIndex]; + } + } + + + if (aLenMain >= 2) + { + m_LongestMatchLength = ReadMatchDistances(); + if (m_LongestMatchLength >= 2 && + ( + (m_LongestMatchLength >= aLenMain && + m_MatchDistances[aLenMain] < aBackMain) || + m_LongestMatchLength == aLenMain + 1 && + !ChangePair(aBackMain, m_MatchDistances[m_LongestMatchLength]) || + m_LongestMatchLength > aLenMain + 1 || + m_LongestMatchLength + 1 >= aLenMain && + ChangePair(m_MatchDistances[aLenMain - 1], aBackMain) + ) + ) + { + m_LongestMatchWasFound = true; + aBackRes = UINT32(-1); + return 1; + } + for(int i = 0; i < kNumRepDistances; i++) + { + UINT32 aRepLen = m_MatchFinder.GetMatchLen(0 - 1, m_RepDistances[i], kMatchMaxLen); + if (aRepLen >= 2 && aRepLen + 1 >= aLenMain) + { + m_LongestMatchWasFound = true; + aBackRes = UINT32(-1); + return 1; + } + } + aBackRes = aBackMain + kNumRepDistances; + MovePos(aLenMain - 2); + return aLenMain; + } + aBackRes = UINT32(-1); + return 1; +} + +HRESULT CEncoder::Flush() +{ + m_RangeEncoder.FlushData(); + return m_RangeEncoder.FlushStream(); +} + +HRESULT CEncoder::CodeReal(ISequentialInStream *anInStream, + ISequentialOutStream *anOutStream, + const UINT64 *anInSize) +{ + RETURN_IF_NOT_S_OK(Create()); + Init(anInStream, anOutStream); + + if (m_MatchFinder.GetNumAvailableBytes() == 0) + return Flush(); + + if (!m_FastMode) + { + FillPosSlotPrices(); + FillDistancesPrices(); + FillAlignPrices(); + } + + m_LenEncoder.SetTableSize(m_NumFastBytes); + m_LenEncoder.UpdateTables(); + m_RepMatchLenEncoder.SetTableSize(m_NumFastBytes); + m_RepMatchLenEncoder.UpdateTables(); + + UINT64 aLastPosSlotFillingPos = 0; + + UINT64 aNowPos64 = 0; + ReadMatchDistances(); + UINT32 aPosState = UINT32(aNowPos64) & m_PosStateMask; + m_MainChoiceEncoders[m_State.m_Index][aPosState].Encode(&m_RangeEncoder, kMainChoiceLiteralIndex); + m_State.UpdateChar(); + BYTE aByte = m_MatchFinder.GetIndexByte(0 - m_AdditionalOffset); + m_LiteralEncoder.Encode(&m_RangeEncoder, UINT32(aNowPos64), m_PreviousByte, false, 0, aByte); + m_PreviousByte = aByte; + m_AdditionalOffset--; + aNowPos64++; + if (m_MatchFinder.GetNumAvailableBytes() == 0) + return Flush(); + while(true) + { + UINT32 aPos; + UINT32 aPosState = UINT32(aNowPos64) & m_PosStateMask; + + UINT32 aLen; + if (m_FastMode) + aLen = GetOptimumFast(aPos, UINT32(aNowPos64)); + else + aLen = GetOptimum(aPos, UINT32(aNowPos64)); + + if(aLen == 1 && aPos == (-1)) + { + m_MainChoiceEncoders[m_State.m_Index][aPosState].Encode(&m_RangeEncoder, kMainChoiceLiteralIndex); + m_State.UpdateChar(); + BYTE aMatchByte; + if(m_PeviousIsMatch) + aMatchByte = m_MatchFinder.GetIndexByte(0 - m_RepDistances[0] - 1 - m_AdditionalOffset); + BYTE aByte = m_MatchFinder.GetIndexByte(0 - m_AdditionalOffset); + m_LiteralEncoder.Encode(&m_RangeEncoder, UINT32(aNowPos64), m_PreviousByte, m_PeviousIsMatch, aMatchByte, aByte); + m_PreviousByte = aByte; + m_PeviousIsMatch = false; + } + else + { + m_PeviousIsMatch = true; + m_MainChoiceEncoders[m_State.m_Index][aPosState].Encode(&m_RangeEncoder, kMainChoiceMatchIndex); + if(aPos < kNumRepDistances) + { + m_MatchChoiceEncoders[m_State.m_Index].Encode(&m_RangeEncoder, kMatchChoiceRepetitionIndex); + if(aPos == 0) + { + m_MatchRepChoiceEncoders[m_State.m_Index].Encode(&m_RangeEncoder, 0); + if(aLen == 1) + m_MatchRepShortChoiceEncoders[m_State.m_Index][aPosState].Encode(&m_RangeEncoder, 0); + else + m_MatchRepShortChoiceEncoders[m_State.m_Index][aPosState].Encode(&m_RangeEncoder, 1); + } + else + { + m_MatchRepChoiceEncoders[m_State.m_Index].Encode(&m_RangeEncoder, 1); + if (aPos == 1) + m_MatchRep1ChoiceEncoders[m_State.m_Index].Encode(&m_RangeEncoder, 0); + else + { + m_MatchRep1ChoiceEncoders[m_State.m_Index].Encode(&m_RangeEncoder, 1); + m_MatchRep2ChoiceEncoders[m_State.m_Index].Encode(&m_RangeEncoder, aPos - 2); + } + } + if (aLen == 1) + m_State.UpdateShortRep(); + else + { + m_RepMatchLenEncoder.Encode(&m_RangeEncoder, aLen - kMatchMinLen, aPosState); + m_State.UpdateRep(); + } + + + UINT32 aDistance = m_RepDistances[aPos]; + if (aPos != 0) + { + for(UINT32 i = aPos; i >= 1; i--) + m_RepDistances[i] = m_RepDistances[i - 1]; + m_RepDistances[0] = aDistance; + } + } + else + { + m_MatchChoiceEncoders[m_State.m_Index].Encode(&m_RangeEncoder, kMatchChoiceDistanceIndex); + m_State.UpdateMatch(); + m_LenEncoder.Encode(&m_RangeEncoder, aLen - kMatchMinLen, aPosState); + aPos -= kNumRepDistances; + UINT32 aPosSlot = GetPosSlot(aPos); + UINT32 aLenToPosState = GetLenToPosState(aLen); + m_PosSlotEncoder[aLenToPosState].Encode(&m_RangeEncoder, aPosSlot); + + UINT32 aFooterBits = kDistDirectBits[aPosSlot]; + UINT32 aPosReduced = aPos - kDistStart[aPosSlot]; + if (aPosSlot >= kStartPosModelIndex) + { + if (aPosSlot < kEndPosModelIndex) + m_PosEncoders[aPosSlot - kStartPosModelIndex].Encode(&m_RangeEncoder, aPosReduced); + else + { + m_RangeEncoder.EncodeDirectBits(aPosReduced >> kNumAlignBits, aFooterBits - kNumAlignBits); + m_PosAlignEncoder.Encode(&m_RangeEncoder, aPosReduced & kAlignMask); + if (!m_FastMode) + if (--m_AlignPriceCount == 0) + FillAlignPrices(); + } + } + UINT32 aDistance = aPos; + for(UINT32 i = kNumRepDistances - 1; i >= 1; i--) + m_RepDistances[i] = m_RepDistances[i - 1]; + m_RepDistances[0] = aDistance; + } + m_PreviousByte = m_MatchFinder.GetIndexByte(aLen - 1 - m_AdditionalOffset); + } + m_AdditionalOffset -= aLen; + aNowPos64 += aLen; + if (!m_FastMode) + if (aNowPos64 - aLastPosSlotFillingPos >= (1 << 9)) + { + FillPosSlotPrices(); + FillDistancesPrices(); + aLastPosSlotFillingPos = aNowPos64; + } + if (m_AdditionalOffset == 0 && m_MatchFinder.GetNumAvailableBytes() == 0) + return Flush(); + } +} + +HRESULT CEncoder::Code(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream, const UINT64 *anInSize) +{ + try { + return CodeReal(anInStream, anOutStream, anInSize); + } catch (HRESULT& e) { + return e; + } catch (...) { + return E_FAIL; + } +} + +void CEncoder::FillPosSlotPrices() +{ + for (int aLenToPosState = 0; aLenToPosState < kNumLenToPosStates; aLenToPosState++) + { + UINT32 aPosSlot; + for (aPosSlot = 0; aPosSlot < kEndPosModelIndex && aPosSlot < m_DistTableSize; aPosSlot++) + m_PosSlotPrices[aLenToPosState][aPosSlot] = m_PosSlotEncoder[aLenToPosState].GetPrice(aPosSlot); + for (; aPosSlot < m_DistTableSize; aPosSlot++) + m_PosSlotPrices[aLenToPosState][aPosSlot] = m_PosSlotEncoder[aLenToPosState].GetPrice(aPosSlot) + + ((kDistDirectBits[aPosSlot] - kNumAlignBits) << kNumBitPriceShiftBits); + } +} + +void CEncoder::FillDistancesPrices() +{ + for (int aLenToPosState = 0; aLenToPosState < kNumLenToPosStates; aLenToPosState++) + { + UINT32 i; + for (i = 0; i < kStartPosModelIndex; i++) + m_DistancesPrices[aLenToPosState][i] = m_PosSlotPrices[aLenToPosState][i]; + for (; i < kNumFullDistances; i++) + { + UINT32 aPosSlot = GetPosSlot(i); + m_DistancesPrices[aLenToPosState][i] = m_PosSlotPrices[aLenToPosState][aPosSlot] + + m_PosEncoders[aPosSlot - kStartPosModelIndex].GetPrice(i - kDistStart[aPosSlot]); + } + } +} + +void CEncoder::FillAlignPrices() +{ + for (int i = 0; i < kAlignTableSize; i++) + m_AlignPrices[i] = m_PosAlignEncoder.GetPrice(i); + m_AlignPriceCount = kAlignTableSize; +} + +}} diff --git a/hostTools/lzma/compress/LZMAEncoder.h b/hostTools/lzma/compress/LZMAEncoder.h new file mode 100644 index 0000000..6368738 --- /dev/null +++ b/hostTools/lzma/compress/LZMAEncoder.h @@ -0,0 +1,228 @@ +#ifndef __LZARITHMETIC_ENCODER_H +#define __LZARITHMETIC_ENCODER_H + +#include "Portable.h" +#include "AriPrice.h" +#include "LZMA.h" +#include "LenCoder.h" +#include "LiteralCoder.h" +#include "AriConst.h" + +// NOTE Here is choosen the MatchFinder +#include "BinTree2.h" +#define MATCH_FINDER NBT2::CMatchFinderBinTree + +namespace NCompress { +namespace NLZMA { + +struct COptimal +{ + CState State; + + bool Prev1IsChar; + bool Prev2; + + UINT32 PosPrev2; + UINT32 BackPrev2; + + UINT32 Price; + UINT32 PosPrev; // posNext; + UINT32 BackPrev; + UINT32 Backs[kNumRepDistances]; + void MakeAsChar() { BackPrev = UINT32(-1); Prev1IsChar = false; } + void MakeAsShortRep() { BackPrev = 0; ; Prev1IsChar = false; } + bool IsShortRep() { return (BackPrev == 0); } +}; + + +extern BYTE g_FastPos[1024]; +inline UINT32 GetPosSlot(UINT32 aPos) +{ + if (aPos < (1 << 10)) + return g_FastPos[aPos]; + if (aPos < (1 << 19)) + return g_FastPos[aPos >> 9] + 18; + return g_FastPos[aPos >> 18] + 36; +} + +inline UINT32 GetPosSlot2(UINT32 aPos) +{ + if (aPos < (1 << 16)) + return g_FastPos[aPos >> 6] + 12; + if (aPos < (1 << 25)) + return g_FastPos[aPos >> 15] + 30; + return g_FastPos[aPos >> 24] + 48; +} + +const int kIfinityPrice = 0xFFFFFFF; + +typedef CMyBitEncoder CMyBitEncoder2; + +const int kNumOpts = 1 << 12; + +class CEncoder : public CBaseCoder +{ + COptimal m_Optimum[kNumOpts]; +public: + MATCH_FINDER m_MatchFinder; + CMyRangeEncoder m_RangeEncoder; +private: + + CMyBitEncoder2 m_MainChoiceEncoders[kNumStates][NLength::kNumPosStatesEncodingMax]; + CMyBitEncoder2 m_MatchChoiceEncoders[kNumStates]; + CMyBitEncoder2 m_MatchRepChoiceEncoders[kNumStates]; + CMyBitEncoder2 m_MatchRep1ChoiceEncoders[kNumStates]; + CMyBitEncoder2 m_MatchRep2ChoiceEncoders[kNumStates]; + CMyBitEncoder2 m_MatchRepShortChoiceEncoders[kNumStates][NLength::kNumPosStatesEncodingMax]; + + CBitTreeEncoder m_PosSlotEncoder[kNumLenToPosStates]; + + CReverseBitTreeEncoder2 m_PosEncoders[kNumPosModels]; + CReverseBitTreeEncoder2 m_PosAlignEncoder; + // CBitTreeEncoder2 m_PosEncoders[kNumPosModels]; + // CBitTreeEncoder2 m_PosAlignEncoder; + + NLength::CPriceTableEncoder m_LenEncoder; + NLength::CPriceTableEncoder m_RepMatchLenEncoder; + + NLiteral::CEncoder m_LiteralEncoder; + + UINT32 m_MatchDistances[kMatchMaxLen + 1]; + + bool m_FastMode; + bool m_MaxMode; + UINT32 m_NumFastBytes; + UINT32 m_LongestMatchLength; + + UINT32 m_AdditionalOffset; + + UINT32 m_OptimumEndIndex; + UINT32 m_OptimumCurrentIndex; + + bool m_LongestMatchWasFound; + + UINT32 m_PosSlotPrices[kNumLenToPosStates][kDistTableSizeMax]; + + UINT32 m_DistancesPrices[kNumLenToPosStates][kNumFullDistances]; + + UINT32 m_AlignPrices[kAlignTableSize]; + UINT32 m_AlignPriceCount; + + UINT32 m_DistTableSize; + + UINT32 m_PosStateBits; + UINT32 m_PosStateMask; + UINT32 m_LiteralPosStateBits; + UINT32 m_LiteralContextBits; + + UINT32 m_DictionarySize; + + + UINT32 m_DictionarySizePrev; + UINT32 m_NumFastBytesPrev; + + + UINT32 ReadMatchDistances() + { + UINT32 aLen = m_MatchFinder.GetLongestMatch(m_MatchDistances); + if (aLen == m_NumFastBytes) + aLen += m_MatchFinder.GetMatchLen(aLen, m_MatchDistances[aLen], + kMatchMaxLen - aLen); + m_AdditionalOffset++; + HRESULT aResult = m_MatchFinder.MovePos(); + if (aResult != S_OK) + throw aResult; + return aLen; + } + + void MovePos(UINT32 aNum); + UINT32 GetRepLen1Price(CState aState, UINT32 aPosState) const + { + return m_MatchRepChoiceEncoders[aState.m_Index].GetPrice(0) + + m_MatchRepShortChoiceEncoders[aState.m_Index][aPosState].GetPrice(0); + } + UINT32 GetRepPrice(UINT32 aRepIndex, UINT32 aLen, CState aState, UINT32 aPosState) const + { + UINT32 aPrice = m_RepMatchLenEncoder.GetPrice(aLen - kMatchMinLen, aPosState); + if(aRepIndex == 0) + { + aPrice += m_MatchRepChoiceEncoders[aState.m_Index].GetPrice(0); + aPrice += m_MatchRepShortChoiceEncoders[aState.m_Index][aPosState].GetPrice(1); + } + else + { + aPrice += m_MatchRepChoiceEncoders[aState.m_Index].GetPrice(1); + if (aRepIndex == 1) + aPrice += m_MatchRep1ChoiceEncoders[aState.m_Index].GetPrice(0); + else + { + aPrice += m_MatchRep1ChoiceEncoders[aState.m_Index].GetPrice(1); + aPrice += m_MatchRep2ChoiceEncoders[aState.m_Index].GetPrice(aRepIndex - 2); + } + } + return aPrice; + } + /* + UINT32 GetPosLen2Price(UINT32 aPos, UINT32 aPosState) const + { + if (aPos >= kNumFullDistances) + return kIfinityPrice; + return m_DistancesPrices[0][aPos] + m_LenEncoder.GetPrice(0, aPosState); + } + UINT32 GetPosLen3Price(UINT32 aPos, UINT32 aLen, UINT32 aPosState) const + { + UINT32 aPrice; + UINT32 aLenToPosState = GetLenToPosState(aLen); + if (aPos < kNumFullDistances) + aPrice = m_DistancesPrices[aLenToPosState][aPos]; + else + aPrice = m_PosSlotPrices[aLenToPosState][GetPosSlot2(aPos)] + + m_AlignPrices[aPos & kAlignMask]; + return aPrice + m_LenEncoder.GetPrice(aLen - kMatchMinLen, aPosState); + } + */ + UINT32 GetPosLenPrice(UINT32 aPos, UINT32 aLen, UINT32 aPosState) const + { + if (aLen == 2 && aPos >= 0x80) + return kIfinityPrice; + UINT32 aPrice; + UINT32 aLenToPosState = GetLenToPosState(aLen); + if (aPos < kNumFullDistances) + aPrice = m_DistancesPrices[aLenToPosState][aPos]; + else + aPrice = m_PosSlotPrices[aLenToPosState][GetPosSlot2(aPos)] + + m_AlignPrices[aPos & kAlignMask]; + return aPrice + m_LenEncoder.GetPrice(aLen - kMatchMinLen, aPosState); + } + + UINT32 Backward(UINT32 &aBackRes, UINT32 aCur); + UINT32 GetOptimum(UINT32 &aBackRes, UINT32 aPosition); + UINT32 GetOptimumFast(UINT32 &aBackRes, UINT32 aPosition); + + void FillPosSlotPrices(); + void FillDistancesPrices(); + void FillAlignPrices(); + + HRESULT Flush(); + + HRESULT Create(); + + HRESULT CodeReal(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream, const UINT64 *anInSize); + + HRESULT Init(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream); + +public: + CEncoder(); + + HRESULT SetEncoderAlgorithm(UINT32 A); + HRESULT SetEncoderNumFastBytes(UINT32 A); + HRESULT SetDictionarySize(UINT32 aDictionarySize); + HRESULT SetLiteralProperties(UINT32 aLiteralPosStateBits, UINT32 aLiteralContextBits); + HRESULT SetPosBitsProperties(UINT32 aNumPosStateBits); + HRESULT Code(ISequentialInStream *anInStream, ISequentialOutStream *anOutStream, const UINT64 *anInSize); + HRESULT WriteCoderProperties(ISequentialOutStream *anOutStream); +}; + +}} + +#endif diff --git a/hostTools/lzma/compress/LenCoder.cpp b/hostTools/lzma/compress/LenCoder.cpp new file mode 100644 index 0000000..35162b2 --- /dev/null +++ b/hostTools/lzma/compress/LenCoder.cpp @@ -0,0 +1,73 @@ +#include "LenCoder.h" + +using namespace NCompression; +using namespace NArithmetic; + +namespace NLength { + +void CEncoder::Init() +{ + m_Choice.Init(); + for (UINT32 aPosState = 0; aPosState < m_NumPosStates; aPosState++) + { + m_LowCoder[aPosState].Init(); + m_MidCoder[aPosState].Init(); + } + m_Choice2.Init(); + m_HighCoder.Init(); +} + +void CEncoder::Encode(CMyRangeEncoder *aRangeEncoder, UINT32 aSymbol, UINT32 aPosState) +{ + if(aSymbol < kNumLowSymbols) + { + m_Choice.Encode(aRangeEncoder, 0); + m_LowCoder[aPosState].Encode(aRangeEncoder, aSymbol); + } + else + { + aSymbol -= kNumLowSymbols; + m_Choice.Encode(aRangeEncoder, 1); + if(aSymbol < kNumMidSymbols) + { + m_Choice2.Encode(aRangeEncoder, 0); + m_MidCoder[aPosState].Encode(aRangeEncoder, aSymbol); + } + else + { + aSymbol -= kNumMidSymbols; + m_Choice2.Encode(aRangeEncoder, 1); + m_HighCoder.Encode(aRangeEncoder, aSymbol); + } + } +} + +UINT32 CEncoder::GetPrice(UINT32 aSymbol, UINT32 aPosState) const +{ + UINT32 aPrice = 0; + if(aSymbol < kNumLowSymbols) + { + aPrice += m_Choice.GetPrice(0); + aPrice += m_LowCoder[aPosState].GetPrice(aSymbol); + } + else + { + aSymbol -= kNumLowSymbols; + aPrice += m_Choice.GetPrice(1); + if(aSymbol < kNumMidSymbols) + { + aPrice += m_Choice2.GetPrice(0); + aPrice += m_MidCoder[aPosState].GetPrice(aSymbol); + } + else + { + aSymbol -= kNumMidSymbols; + aPrice += m_Choice2.GetPrice(1); + aPrice += m_HighCoder.GetPrice(aSymbol); + } + } + return aPrice; +} + +} + diff --git a/hostTools/lzma/compress/LenCoder.h b/hostTools/lzma/compress/LenCoder.h new file mode 100644 index 0000000..ff389b9 --- /dev/null +++ b/hostTools/lzma/compress/LenCoder.h @@ -0,0 +1,122 @@ +#ifndef __LENCODER_H +#define __LENCODER_H + +#include "BitTreeCoder.h" + +namespace NLength { + +const int kNumPosStatesBitsMax = 4; +const int kNumPosStatesMax = (1 << kNumPosStatesBitsMax); + + +const int kNumPosStatesBitsEncodingMax = 4; +const int kNumPosStatesEncodingMax = (1 << kNumPosStatesBitsEncodingMax); + + +const int kNumMoveBits = 5; + +const int kNumLenBits = 3; +const int kNumLowSymbols = 1 << kNumLenBits; +const int kNumMidBits = 3; +const int kNumMidSymbols = 1 << kNumMidBits; + +const int kNumHighBits = 8; + +const int kNumSymbolsTotal = kNumLowSymbols + kNumMidSymbols + (1 << kNumHighBits); + +class CEncoder +{ + CMyBitEncoder m_Choice; + CBitTreeEncoder m_LowCoder[kNumPosStatesEncodingMax]; + CMyBitEncoder m_Choice2; + CBitTreeEncoder m_MidCoder[kNumPosStatesEncodingMax]; + CBitTreeEncoder m_HighCoder; +protected: + UINT32 m_NumPosStates; +public: + void Create(UINT32 aNumPosStates) + { m_NumPosStates = aNumPosStates; } + void Init(); + void Encode(CMyRangeEncoder *aRangeEncoder, UINT32 aSymbol, UINT32 aPosState); + + UINT32 GetPrice(UINT32 aSymbol, UINT32 aPosState) const; +}; + +const int kNumSpecSymbols = kNumLowSymbols + kNumMidSymbols; + +class CPriceTableEncoder: public CEncoder +{ + UINT32 m_Prices[kNumSymbolsTotal][kNumPosStatesEncodingMax]; + UINT32 m_TableSize; + UINT32 m_Counters[kNumPosStatesEncodingMax]; +public: + void SetTableSize(UINT32 aTableSize) + { m_TableSize = aTableSize; } + UINT32 GetPrice(UINT32 aSymbol, UINT32 aPosState) const + { return m_Prices[aSymbol][aPosState]; } + void UpdateTable(UINT32 aPosState) + { + for (UINT32 aLen = 0; aLen < m_TableSize; aLen++) + m_Prices[aLen][aPosState] = CEncoder::GetPrice(aLen , aPosState); + m_Counters[aPosState] = m_TableSize; + } + void UpdateTables() + { + for (UINT32 aPosState = 0; aPosState < m_NumPosStates; aPosState++) + UpdateTable(aPosState); + } + void Encode(CMyRangeEncoder *aRangeEncoder, UINT32 aSymbol, UINT32 aPosState) + { + CEncoder::Encode(aRangeEncoder, aSymbol, aPosState); + if (--m_Counters[aPosState] == 0) + UpdateTable(aPosState); + } +}; + + +class CDecoder +{ + CMyBitDecoder m_Choice; + CBitTreeDecoder m_LowCoder[kNumPosStatesMax]; + CMyBitDecoder m_Choice2; + CBitTreeDecoder m_MidCoder[kNumPosStatesMax]; + CBitTreeDecoder m_HighCoder; + UINT32 m_NumPosStates; +public: + void Create(UINT32 aNumPosStates) + { m_NumPosStates = aNumPosStates; } + void Init() + { + m_Choice.Init(); + for (UINT32 aPosState = 0; aPosState < m_NumPosStates; aPosState++) + { + m_LowCoder[aPosState].Init(); + m_MidCoder[aPosState].Init(); + } + m_Choice2.Init(); + m_HighCoder.Init(); + } + UINT32 Decode(CMyRangeDecoder *aRangeDecoder, UINT32 aPosState) + { + if(m_Choice.Decode(aRangeDecoder) == 0) + return m_LowCoder[aPosState].Decode(aRangeDecoder); + else + { + UINT32 aSymbol = kNumLowSymbols; + if(m_Choice2.Decode(aRangeDecoder) == 0) + aSymbol += m_MidCoder[aPosState].Decode(aRangeDecoder); + else + { + aSymbol += kNumMidSymbols; + aSymbol += m_HighCoder.Decode(aRangeDecoder); + } + return aSymbol; + } + } + +}; + +} + + +#endif diff --git a/hostTools/lzma/compress/LiteralCoder.cpp b/hostTools/lzma/compress/LiteralCoder.cpp new file mode 100644 index 0000000..fdb4fe3 --- /dev/null +++ b/hostTools/lzma/compress/LiteralCoder.cpp @@ -0,0 +1,66 @@ +#include "LiteralCoder.h" + +using namespace NCompression; +using namespace NArithmetic; + +namespace NLiteral { + +void CEncoder2::Init() +{ + for (int i = 0; i < 3; i++) + for (int j = 1; j < (1 << 8); j++) + m_Encoders[i][j].Init(); +} + +void CEncoder2::Encode(CMyRangeEncoder *aRangeEncoder, + bool aMatchMode, BYTE aMatchByte, BYTE aSymbol) +{ + UINT32 aContext = 1; + bool aSame = true; + for (int i = 7; i >= 0; i--) + { + UINT32 aBit = (aSymbol >> i) & 1; + unsigned aState; + if (aMatchMode && aSame) + { + UINT32 aMatchBit = (aMatchByte >> i) & 1; + aState = 1 + aMatchBit; + aSame = (aMatchBit == aBit); + } + else + aState = 0; + m_Encoders[aState][aContext].Encode(aRangeEncoder, aBit); + aContext = (aContext << 1) | aBit; + } +} + +UINT32 CEncoder2::GetPrice(bool aMatchMode, BYTE aMatchByte, BYTE aSymbol) const +{ + UINT32 aPrice = 0; + UINT32 aContext = 1; + int i = 7; + if (aMatchMode) + { + for (; i >= 0; i--) + { + UINT32 aMatchBit = (aMatchByte >> i) & 1; + UINT32 aBit = (aSymbol >> i) & 1; + aPrice += m_Encoders[1 + aMatchBit][aContext].GetPrice(aBit); + aContext = (aContext << 1) | aBit; + if (aMatchBit != aBit) + { + i--; + break; + } + } + } + for (; i >= 0; i--) + { + UINT32 aBit = (aSymbol >> i) & 1; + aPrice += m_Encoders[0][aContext].GetPrice(aBit); + aContext = (aContext << 1) | aBit; + } + return aPrice; +}; + +} diff --git a/hostTools/lzma/compress/LiteralCoder.h b/hostTools/lzma/compress/LiteralCoder.h new file mode 100644 index 0000000..147bf03 --- /dev/null +++ b/hostTools/lzma/compress/LiteralCoder.h @@ -0,0 +1,160 @@ +#ifndef __LITERALCODER_H +#define __LITERALCODER_H + +#include "AriBitCoder.h" +#include "RCDefs.h" + +namespace NLiteral { + +const int kNumMoveBits = 5; + +class CEncoder2 +{ + CMyBitEncoder m_Encoders[3][1 << 8]; +public: + void Init(); + void Encode(CMyRangeEncoder *aRangeEncoder, bool aMatchMode, BYTE aMatchByte, BYTE aSymbol); + UINT32 GetPrice(bool aMatchMode, BYTE aMatchByte, BYTE aSymbol) const; +}; + +class CDecoder2 +{ + CMyBitDecoder m_Decoders[3][1 << 8]; +public: + void Init() + { + for (int i = 0; i < 3; i++) + for (int j = 1; j < (1 << 8); j++) + m_Decoders[i][j].Init(); + } + + BYTE DecodeNormal(CMyRangeDecoder *aRangeDecoder) + { + UINT32 aSymbol = 1; + RC_INIT_VAR + do + { + // aSymbol = (aSymbol << 1) | m_Decoders[0][aSymbol].Decode(aRangeDecoder); + RC_GETBIT(kNumMoveBits, m_Decoders[0][aSymbol].m_Probability, aSymbol) + } + while (aSymbol < 0x100); + RC_FLUSH_VAR + return aSymbol; + } + + BYTE DecodeWithMatchByte(CMyRangeDecoder *aRangeDecoder, BYTE aMatchByte) + { + UINT32 aSymbol = 1; + RC_INIT_VAR + do + { + UINT32 aMatchBit = (aMatchByte >> 7) & 1; + aMatchByte <<= 1; + // UINT32 aBit = m_Decoders[1 + aMatchBit][aSymbol].Decode(aRangeDecoder); + // aSymbol = (aSymbol << 1) | aBit; + UINT32 aBit; + RC_GETBIT2(kNumMoveBits, m_Decoders[1 + aMatchBit][aSymbol].m_Probability, aSymbol, + aBit = 0, aBit = 1) + if (aMatchBit != aBit) + { + while (aSymbol < 0x100) + { + // aSymbol = (aSymbol << 1) | m_Decoders[0][aSymbol].Decode(aRangeDecoder); + RC_GETBIT(kNumMoveBits, m_Decoders[0][aSymbol].m_Probability, aSymbol) + } + break; + } + } + while (aSymbol < 0x100); + RC_FLUSH_VAR + return aSymbol; + } +}; + +/* +const UINT32 kNumPrevByteBits = 1; +const UINT32 kNumPrevByteStates = (1 << kNumPrevByteBits); + +inline UINT32 GetLiteralState(BYTE aPrevByte) + { return (aPrevByte >> (8 - kNumPrevByteBits)); } +*/ + +class CEncoder +{ + CEncoder2 *m_Coders; + UINT32 m_NumPrevBits; + UINT32 m_NumPosBits; + UINT32 m_PosMask; +public: + CEncoder(): m_Coders(0) {} + ~CEncoder() { Free(); } + void Free() + { + delete []m_Coders; + m_Coders = 0; + } + void Create(UINT32 aNumPosBits, UINT32 aNumPrevBits) + { + Free(); + m_NumPosBits = aNumPosBits; + m_PosMask = (1 << aNumPosBits) - 1; + m_NumPrevBits = aNumPrevBits; + UINT32 aNumStates = 1 << (m_NumPrevBits + m_NumPosBits); + m_Coders = new CEncoder2[aNumStates]; + } + void Init() + { + UINT32 aNumStates = 1 << (m_NumPrevBits + m_NumPosBits); + for (UINT32 i = 0; i < aNumStates; i++) + m_Coders[i].Init(); + } + UINT32 GetState(UINT32 aPos, BYTE aPrevByte) const + { return ((aPos & m_PosMask) << m_NumPrevBits) + (aPrevByte >> (8 - m_NumPrevBits)); } + void Encode(CMyRangeEncoder *aRangeEncoder, UINT32 aPos, BYTE aPrevByte, + bool aMatchMode, BYTE aMatchByte, BYTE aSymbol) + { m_Coders[GetState(aPos, aPrevByte)].Encode(aRangeEncoder, aMatchMode, + aMatchByte, aSymbol); } + UINT32 GetPrice(UINT32 aPos, BYTE aPrevByte, bool aMatchMode, BYTE aMatchByte, BYTE aSymbol) const + { return m_Coders[GetState(aPos, aPrevByte)].GetPrice(aMatchMode, aMatchByte, aSymbol); } +}; + +class CDecoder +{ + CDecoder2 *m_Coders; + UINT32 m_NumPrevBits; + UINT32 m_NumPosBits; + UINT32 m_PosMask; +public: + CDecoder(): m_Coders(0) {} + ~CDecoder() { Free(); } + void Free() + { + delete []m_Coders; + m_Coders = 0; + } + void Create(UINT32 aNumPosBits, UINT32 aNumPrevBits) + { + Free(); + m_NumPosBits = aNumPosBits; + m_PosMask = (1 << aNumPosBits) - 1; + m_NumPrevBits = aNumPrevBits; + UINT32 aNumStates = 1 << (m_NumPrevBits + m_NumPosBits); + m_Coders = new CDecoder2[aNumStates]; + } + void Init() + { + UINT32 aNumStates = 1 << (m_NumPrevBits + m_NumPosBits); + for (UINT32 i = 0; i < aNumStates; i++) + m_Coders[i].Init(); + } + UINT32 GetState(UINT32 aPos, BYTE aPrevByte) const + { return ((aPos & m_PosMask) << m_NumPrevBits) + (aPrevByte >> (8 - m_NumPrevBits)); } + BYTE DecodeNormal(CMyRangeDecoder *aRangeDecoder, UINT32 aPos, BYTE aPrevByte) + { return m_Coders[GetState(aPos, aPrevByte)].DecodeNormal(aRangeDecoder); } + BYTE DecodeWithMatchByte(CMyRangeDecoder *aRangeDecoder, UINT32 aPos, BYTE aPrevByte, BYTE aMatchByte) + { return m_Coders[GetState(aPos, aPrevByte)].DecodeWithMatchByte(aRangeDecoder, aMatchByte); } +}; + +} + +#endif diff --git a/hostTools/lzma/compress/OutByte.cpp b/hostTools/lzma/compress/OutByte.cpp new file mode 100644 index 0000000..a658798 --- /dev/null +++ b/hostTools/lzma/compress/OutByte.cpp @@ -0,0 +1,45 @@ +#include "OutByte.h" + +namespace NStream { + +COutByte::COutByte(UINT32 aBufferSize): + m_BufferSize(aBufferSize) +{ + m_Buffer = new BYTE[m_BufferSize]; +} + +COutByte::~COutByte() +{ + delete []m_Buffer; +} + +void COutByte::Init(ISequentialOutStream *aStream) +{ + m_Stream = aStream; + m_ProcessedSize = 0; + m_Pos = 0; +} + +HRESULT COutByte::Flush() +{ + if (m_Pos == 0) + return S_OK; + UINT32 aProcessedSize; + HRESULT aResult = m_Stream->Write(m_Buffer, m_Pos, &aProcessedSize); + if (aResult != S_OK) + return aResult; + if (m_Pos != aProcessedSize) + return E_FAIL; + m_ProcessedSize += aProcessedSize; + m_Pos = 0; + return S_OK; +} + +void COutByte::WriteBlock() +{ + HRESULT aResult = Flush(); + if (aResult != S_OK) + throw aResult; +} + +} diff --git a/hostTools/lzma/compress/OutByte.h b/hostTools/lzma/compress/OutByte.h new file mode 100644 index 0000000..dc9ff0a --- /dev/null +++ b/hostTools/lzma/compress/OutByte.h @@ -0,0 +1,42 @@ +#ifndef __STREAM_OUTBYTE_H +#define __STREAM_OUTBYTE_H + +#include "Portable.h" +#include "IInOutStreams.h" + +namespace NStream { + +class COutByte +{ + BYTE *m_Buffer; + UINT32 m_Pos; + UINT32 m_BufferSize; + ISequentialOutStream* m_Stream; + UINT64 m_ProcessedSize; + + void WriteBlock(); +public: + COutByte(UINT32 aBufferSize = (1 << 20)); + ~COutByte(); + + void Init(ISequentialOutStream *aStream); + HRESULT Flush(); + + void WriteByte(BYTE aByte) + { + m_Buffer[m_Pos++] = aByte; + if(m_Pos >= m_BufferSize) + WriteBlock(); + } + void WriteBytes(const void *aBytes, UINT32 aSize) + { + for (UINT32 i = 0; i < aSize; i++) + WriteByte(((const BYTE *)aBytes)[i]); + } + + UINT64 GetProcessedSize() const { return m_ProcessedSize + m_Pos; } +}; + +} + +#endif diff --git a/hostTools/lzma/compress/Portable.h b/hostTools/lzma/compress/Portable.h new file mode 100644 index 0000000..1985b1b --- /dev/null +++ b/hostTools/lzma/compress/Portable.h @@ -0,0 +1,48 @@ +#ifndef __PORTABLE_H +#define __PORTABLE_H + +#include + +typedef signed char INT8; +typedef unsigned char UINT8; +typedef short INT16; +typedef unsigned short UINT16; +typedef long INT32; +typedef unsigned long UINT32; +#if GNU +typedef long long INT64; +typedef unsigned long long UINT64; +#else +typedef __int64 INT64; +typedef unsigned __int64 UINT64; +#endif + +typedef UINT8 BYTE; +typedef UINT16 WORD; +typedef UINT32 DWORD; + +typedef unsigned UINT_PTR; + +typedef int BOOL; +#define FALSE 0 +#define TRUE 1 + +#define HRESULT int +#define S_OK 0 +#define E_INVALIDARG -1 +#define E_OUTOFMEMORY -2 +#define E_FAIL -3 +#define E_INTERNAL_ERROR -4 +#define E_INVALIDDATA -5 + +template inline T MyMin(T a, T b) { + return a < b ? a : b; +} + +template inline T MyMax(T a, T b) { + return a > b ? a : b; +} + +#define RETURN_IF_NOT_S_OK(x) { HRESULT __aResult_ = (x); if(__aResult_ != S_OK) return __aResult_; } + +#endif diff --git a/hostTools/lzma/compress/RCDefs.h b/hostTools/lzma/compress/RCDefs.h new file mode 100644 index 0000000..326f5f3 --- /dev/null +++ b/hostTools/lzma/compress/RCDefs.h @@ -0,0 +1,42 @@ +#ifndef __RCDEFS_H +#define __RCDEFS_H + +#include "AriBitCoder.h" +#include "AriConst.h" + +#define RC_INIT_VAR \ + UINT32 aRange = aRangeDecoder->m_Range; \ + UINT32 aCode = aRangeDecoder->m_Code; + +#define RC_FLUSH_VAR \ + aRangeDecoder->m_Range = aRange; \ + aRangeDecoder->m_Code = aCode; + +#define RC_NORMALIZE \ + if (aRange < NCompression::NArithmetic::kTopValue) \ + { \ + aCode = (aCode << 8) | aRangeDecoder->m_Stream.ReadByte(); \ + aRange <<= 8; } + +#define RC_GETBIT2(aNumMoveBits, aProb, aModelIndex, Action0, Action1) \ + {UINT32 aNewBound = (aRange >> NCompression::NArithmetic::kNumBitModelTotalBits) * aProb; \ + if (aCode < aNewBound) \ + { \ + Action0; \ + aRange = aNewBound; \ + aProb += (NCompression::NArithmetic::kBitModelTotal - aProb) >> aNumMoveBits; \ + aModelIndex <<= 1; \ + } \ + else \ + { \ + Action1; \ + aRange -= aNewBound; \ + aCode -= aNewBound; \ + aProb -= (aProb) >> aNumMoveBits; \ + aModelIndex = (aModelIndex << 1) + 1; \ + }} \ + RC_NORMALIZE + +#define RC_GETBIT(aNumMoveBits, aProb, aModelIndex) RC_GETBIT2(aNumMoveBits, aProb, aModelIndex, ; , ;) + +#endif diff --git a/hostTools/lzma/compress/RangeCoder.h b/hostTools/lzma/compress/RangeCoder.h new file mode 100644 index 0000000..a9e30f5 --- /dev/null +++ b/hostTools/lzma/compress/RangeCoder.h @@ -0,0 +1,232 @@ +#ifndef __COMPRESSION_RANGECODER_H +#define __COMPRESSION_RANGECODER_H + +#include "InByte.h" +#include "OutByte.h" + +namespace NCompression { +namespace NArithmetic { + +const UINT32 kNumTopBits = 24; +const UINT32 kTopValue = (1 << kNumTopBits); + +class CRangeEncoder +{ + NStream::COutByte m_Stream; + UINT64 m_Low; + UINT32 m_Range; + UINT32 m_FFNum; + BYTE m_Cache; + +public: + void Init(ISequentialOutStream *aStream) + { + m_Stream.Init(aStream); + m_Low = 0; + m_Range = UINT32(-1); + m_FFNum = 0; + m_Cache = 0; + } + + void FlushData() + { + // m_Low += 1; + for(int i = 0; i < 5; i++) + ShiftLow(); + } + + HRESULT FlushStream() + { return m_Stream.Flush(); } + + void Encode(UINT32 aStart, UINT32 aSize, UINT32 aTotal) + { + m_Low += aStart * (m_Range /= aTotal); + m_Range *= aSize; + while (m_Range < kTopValue) + { + m_Range <<= 8; + ShiftLow(); + } + } + + /* + void EncodeDirectBitsDiv(UINT32 aValue, UINT32 aNumTotalBits) + { + m_Low += aValue * (m_Range >>= aNumTotalBits); + Normalize(); + } + + void EncodeDirectBitsDiv2(UINT32 aValue, UINT32 aNumTotalBits) + { + if (aNumTotalBits <= kNumBottomBits) + EncodeDirectBitsDiv(aValue, aNumTotalBits); + else + { + EncodeDirectBitsDiv(aValue >> kNumBottomBits, (aNumTotalBits - kNumBottomBits)); + EncodeDirectBitsDiv(aValue & ((1 << kBottomValueBits) - 1), kNumBottomBits); + } + } + */ + void ShiftLow() + { + if (m_Low < (UINT32)0xFF000000 || UINT32(m_Low >> 32) == 1) + { + m_Stream.WriteByte(m_Cache + BYTE(m_Low >> 32)); + for (;m_FFNum != 0; m_FFNum--) + m_Stream.WriteByte(0xFF + BYTE(m_Low >> 32)); + m_Cache = BYTE(UINT32(m_Low) >> 24); + } + else + m_FFNum++; + m_Low = UINT32(m_Low) << 8; + } + + void EncodeDirectBits(UINT32 aValue, UINT32 aNumTotalBits) + { + for (int i = aNumTotalBits - 1; i >= 0; i--) + { + m_Range >>= 1; + if (((aValue >> i) & 1) == 1) + m_Low += m_Range; + if (m_Range < kTopValue) + { + m_Range <<= 8; + ShiftLow(); + } + } + } + + void EncodeBit(UINT32 aSize0, UINT32 aNumTotalBits, UINT32 aSymbol) + { + UINT32 aNewBound = (m_Range >> aNumTotalBits) * aSize0; + if (aSymbol == 0) + m_Range = aNewBound; + else + { + m_Low += aNewBound; + m_Range -= aNewBound; + } + while (m_Range < kTopValue) + { + m_Range <<= 8; + ShiftLow(); + } + } + + UINT64 GetProcessedSize() { return m_Stream.GetProcessedSize() + m_FFNum; } +}; + +class CRangeDecoder +{ +public: + NStream::CInByte m_Stream; + UINT32 m_Range; + UINT32 m_Code; + UINT32 m_Word; + void Normalize() + { + while (m_Range < kTopValue) + { + m_Code = (m_Code << 8) | m_Stream.ReadByte(); + m_Range <<= 8; + } + } + + void Init(ISequentialInStream *aStream) + { + m_Stream.Init(aStream); + m_Code = 0; + m_Range = UINT32(-1); + for(int i = 0; i < 5; i++) + m_Code = (m_Code << 8) | m_Stream.ReadByte(); + } + + UINT32 GetThreshold(UINT32 aTotal) + { + return (m_Code) / ( m_Range /= aTotal); + } + + void Decode(UINT32 aStart, UINT32 aSize, UINT32 aTotal) + { + m_Code -= aStart * m_Range; + m_Range *= aSize; + Normalize(); + } + + /* + UINT32 DecodeDirectBitsDiv(UINT32 aNumTotalBits) + { + m_Range >>= aNumTotalBits; + UINT32 aThreshold = m_Code / m_Range; + m_Code -= aThreshold * m_Range; + + Normalize(); + return aThreshold; + } + + UINT32 DecodeDirectBitsDiv2(UINT32 aNumTotalBits) + { + if (aNumTotalBits <= kNumBottomBits) + return DecodeDirectBitsDiv(aNumTotalBits); + UINT32 aResult = DecodeDirectBitsDiv(aNumTotalBits - kNumBottomBits) << kNumBottomBits; + return (aResult | DecodeDirectBitsDiv(kNumBottomBits)); + } + */ + + UINT32 DecodeDirectBits(UINT32 aNumTotalBits) + { + UINT32 aRange = m_Range; + UINT32 aCode = m_Code; + UINT32 aResult = 0; + for (UINT32 i = aNumTotalBits; i > 0; i--) + { + aRange >>= 1; + /* + aResult <<= 1; + if (aCode >= aRange) + { + aCode -= aRange; + aResult |= 1; + } + */ + UINT32 t = (aCode - aRange) >> 31; + aCode -= aRange & (t - 1); + // aRange = aRangeTmp + ((aRange & 1) & (1 - t)); + aResult = (aResult << 1) | (1 - t); + + if (aRange < kTopValue) + { + aCode = (aCode << 8) | m_Stream.ReadByte(); + aRange <<= 8; + } + } + m_Range = aRange; + m_Code = aCode; + return aResult; + } + + UINT32 DecodeBit(UINT32 aSize0, UINT32 aNumTotalBits) + { + UINT32 aNewBound = (m_Range >> aNumTotalBits) * aSize0; + UINT32 aSymbol; + if (m_Code < aNewBound) + { + aSymbol = 0; + m_Range = aNewBound; + } + else + { + aSymbol = 1; + m_Code -= aNewBound; + m_Range -= aNewBound; + } + Normalize(); + return aSymbol; + } + + UINT64 GetProcessedSize() {return m_Stream.GetProcessedSize(); } +}; + +}} + +#endif diff --git a/hostTools/lzma/compress/StdAfx.cpp b/hostTools/lzma/compress/StdAfx.cpp new file mode 100644 index 0000000..3ea4c90 --- /dev/null +++ b/hostTools/lzma/compress/StdAfx.cpp @@ -0,0 +1,8 @@ +// stdafx.cpp : source file that includes just the standard includes +// ProgramStore.pch will be the pre-compiled header +// stdafx.obj will contain the pre-compiled type information + +#include "StdAfx.h" + +// TODO: reference any additional headers you need in STDAFX.H +// and not in this file diff --git a/hostTools/lzma/compress/StdAfx.h b/hostTools/lzma/compress/StdAfx.h new file mode 100644 index 0000000..8c419c9 --- /dev/null +++ b/hostTools/lzma/compress/StdAfx.h @@ -0,0 +1,22 @@ +// stdafx.h : include file for standard system include files, +// or project specific include files that are used frequently, but +// are changed infrequently +// + +#if !defined(AFX_STDAFX_H__FF26AFB2_1227_11D4_A62F_00C04F69DA2B__INCLUDED_) +#define AFX_STDAFX_H__FF26AFB2_1227_11D4_A62F_00C04F69DA2B__INCLUDED_ + +#if _MSC_VER > 1000 +#pragma once +#endif // _MSC_VER > 1000 + +#define WIN32_LEAN_AND_MEAN // Exclude rarely-used stuff from Windows headers + +#include + +// TODO: reference additional headers your program requires here + +//{{AFX_INSERT_LOCATION}} +// Microsoft Visual C++ will insert additional declarations immediately before the previous line. + +#endif // !defined(AFX_STDAFX_H__FF26AFB2_1227_11D4_A62F_00C04F69DA2B__INCLUDED_) diff --git a/hostTools/lzma/compress/WindowIn.cpp b/hostTools/lzma/compress/WindowIn.cpp new file mode 100644 index 0000000..20b0859 --- /dev/null +++ b/hostTools/lzma/compress/WindowIn.cpp @@ -0,0 +1,97 @@ +#include "Portable.h" +#include "WindowIn.h" + +namespace NStream { +namespace NWindow { + +CIn::CIn(): + m_BufferBase(0) +{} + +void CIn::Free() +{ + delete []m_BufferBase; + m_BufferBase = 0; +} + +void CIn::Create(UINT32 aKeepSizeBefore, UINT32 aKeepSizeAfter, UINT32 aKeepSizeReserv) +{ + m_KeepSizeBefore = aKeepSizeBefore; + m_KeepSizeAfter = aKeepSizeAfter; + m_KeepSizeReserv = aKeepSizeReserv; + m_BlockSize = aKeepSizeBefore + aKeepSizeAfter + aKeepSizeReserv; + Free(); + m_BufferBase = new BYTE[m_BlockSize]; + m_PointerToLastSafePosition = m_BufferBase + m_BlockSize - aKeepSizeAfter; +} + +CIn::~CIn() +{ + Free(); +} + +HRESULT CIn::Init(ISequentialInStream *aStream) +{ + m_Stream = aStream; + m_Buffer = m_BufferBase; + m_Pos = 0; + m_StreamPos = 0; + m_StreamEndWasReached = false; + return ReadBlock(); +} + +/////////////////////////////////////////// +// ReadBlock + +// In State: +// (m_Buffer + m_StreamPos) <= (m_BufferBase + m_BlockSize) +// Out State: +// m_PosLimit <= m_BlockSize - m_KeepSizeAfter; +// if(m_StreamEndWasReached == false): +// m_StreamPos >= m_Pos + m_KeepSizeAfter +// m_PosLimit = m_StreamPos - m_KeepSizeAfter; +// else +// + +HRESULT CIn::ReadBlock() +{ + if(m_StreamEndWasReached) + return S_OK; + while(true) + { + UINT32 aSize = (m_BufferBase + m_BlockSize) - (m_Buffer + m_StreamPos); + if(aSize == 0) + return S_OK; + UINT32 aNumReadBytes; + RETURN_IF_NOT_S_OK(m_Stream->Read(m_Buffer + m_StreamPos, + aSize, &aNumReadBytes)); + if(aNumReadBytes == 0) + { + m_PosLimit = m_StreamPos; + const BYTE *aPointerToPostion = m_Buffer + m_PosLimit; + if(aPointerToPostion > m_PointerToLastSafePosition) + m_PosLimit = m_PointerToLastSafePosition - m_Buffer; + m_StreamEndWasReached = true; + return S_OK; + } + m_StreamPos += aNumReadBytes; + if(m_StreamPos >= m_Pos + m_KeepSizeAfter) + { + m_PosLimit = m_StreamPos - m_KeepSizeAfter; + return S_OK; + } + } +} + +void CIn::MoveBlock() +{ + BeforeMoveBlock(); + UINT32 anOffset = (m_Buffer + m_Pos - m_KeepSizeBefore) - m_BufferBase; + UINT32 aNumBytes = (m_Buffer + m_StreamPos) - (m_BufferBase + anOffset); + memmove(m_BufferBase, m_BufferBase + anOffset, aNumBytes); + m_Buffer -= anOffset; + AfterMoveBlock(); +} + + +}} diff --git a/hostTools/lzma/compress/WindowIn.h b/hostTools/lzma/compress/WindowIn.h new file mode 100644 index 0000000..039e507 --- /dev/null +++ b/hostTools/lzma/compress/WindowIn.h @@ -0,0 +1,91 @@ +#ifndef __STREAM_WINDOWIN_H +#define __STREAM_WINDOWIN_H + +#include "IInOutStreams.h" + +namespace NStream { +namespace NWindow { + +class CIn +{ + BYTE *m_BufferBase; // pointer to buffer with data + ISequentialInStream* m_Stream; + UINT32 m_PosLimit; // offset (from m_Buffer) of first byte when new block reading must be done + bool m_StreamEndWasReached; // if (true) then m_StreamPos shows real end of stream + + const BYTE *m_PointerToLastSafePosition; + +protected: + BYTE *m_Buffer; // Pointer to virtual Buffer begin + UINT32 m_BlockSize; // Size of Allocated memory block + UINT32 m_Pos; // offset (from m_Buffer) of curent byte + UINT32 m_KeepSizeBefore; // how many BYTEs must be kept in buffer before m_Pos + UINT32 m_KeepSizeAfter; // how many BYTEs must be kept buffer after m_Pos + UINT32 m_KeepSizeReserv; // how many BYTEs must be kept as reserv + UINT32 m_StreamPos; // offset (from m_Buffer) of first not read byte from Stream + + virtual void BeforeMoveBlock() {}; + virtual void AfterMoveBlock() {}; + void MoveBlock(); + virtual HRESULT ReadBlock(); + void Free(); +public: + CIn(); + void Create(UINT32 aKeepSizeBefore, UINT32 aKeepSizeAfter, + UINT32 aKeepSizeReserv = (1<<17)); + virtual ~CIn(); + + HRESULT Init(ISequentialInStream *aStream); + + BYTE *GetBuffer() const { return m_Buffer; } + + const BYTE *GetPointerToCurrentPos() const { return m_Buffer + m_Pos; } + + HRESULT MovePos() + { + m_Pos++; + if (m_Pos > m_PosLimit) + { + const BYTE *aPointerToPostion = m_Buffer + m_Pos; + if(aPointerToPostion > m_PointerToLastSafePosition) + MoveBlock(); + return ReadBlock(); + } + else + return S_OK; + } + // BYTE GetCurrentByte()const; + BYTE GetIndexByte(UINT32 anIndex)const + { return m_Buffer[m_Pos + anIndex]; } + + // UINT32 GetCurPos()const { return m_Pos;}; + // BYTE *GetBufferBeg()const { return m_Buffer;}; + + // aIndex + aLimit have not to exceed m_KeepSizeAfter; + UINT32 GetMatchLen(UINT32 aIndex, UINT32 aBack, UINT32 aLimit) const + { + if(m_StreamEndWasReached) + if ((m_Pos + aIndex) + aLimit > m_StreamPos) + aLimit = m_StreamPos - (m_Pos + aIndex); + aBack++; + BYTE *pby = m_Buffer + m_Pos + aIndex; + UINT32 i; + for(i = 0; i < aLimit && pby[i] == pby[i - aBack]; i++); + return i; + } + + UINT32 GetNumAvailableBytes() const { return m_StreamPos - m_Pos; } + + void ReduceOffsets(UINT32 aSubValue) + { + m_Buffer += aSubValue; + m_PosLimit -= aSubValue; + m_Pos -= aSubValue; + m_StreamPos -= aSubValue; + } + +}; + +}} + +#endif diff --git a/hostTools/lzma/compress/WindowOut.cpp b/hostTools/lzma/compress/WindowOut.cpp new file mode 100644 index 0000000..aad4af6 --- /dev/null +++ b/hostTools/lzma/compress/WindowOut.cpp @@ -0,0 +1,71 @@ +#include "WindowOut.h" + +namespace NStream { +namespace NWindow { + +void COut::Create(UINT32 aKeepSizeBefore, UINT32 aKeepSizeAfter, UINT32 aKeepSizeReserv) +{ + m_Pos = 0; + m_PosLimit = aKeepSizeReserv + aKeepSizeBefore; + m_KeepSizeBefore = aKeepSizeBefore; + m_KeepSizeAfter = aKeepSizeAfter; + m_KeepSizeReserv = aKeepSizeReserv; + m_StreamPos = 0; + m_MoveFrom = m_KeepSizeReserv; + m_WindowSize = aKeepSizeBefore; + UINT32 aBlockSize = m_KeepSizeBefore + m_KeepSizeAfter + m_KeepSizeReserv; + delete []m_Buffer; + m_Buffer = new BYTE[aBlockSize]; +} + +COut::~COut() +{ + delete []m_Buffer; +} + +void COut::SetWindowSize(UINT32 aWindowSize) +{ + m_WindowSize = aWindowSize; + m_MoveFrom = m_KeepSizeReserv + m_KeepSizeBefore - aWindowSize; +} + +void COut::Init(ISequentialOutStream *aStream, bool aSolid) +{ + m_Stream = aStream; + + if(aSolid) + m_StreamPos = m_Pos; + else + { + m_Pos = 0; + m_PosLimit = m_KeepSizeReserv + m_KeepSizeBefore; + m_StreamPos = 0; + } +} + +HRESULT COut::Flush() +{ + UINT32 aSize = m_Pos - m_StreamPos; + if(aSize == 0) + return S_OK; + UINT32 aProcessedSize; + HRESULT aResult = m_Stream->Write(m_Buffer + m_StreamPos, aSize, &aProcessedSize); + if (aResult != S_OK) + return aResult; + if (aSize != aProcessedSize) + return E_FAIL; + m_StreamPos = m_Pos; + return S_OK; +} + +void COut::MoveBlockBackward() +{ + HRESULT aResult = Flush(); + if (aResult != S_OK) + throw aResult; + memmove(m_Buffer, m_Buffer + m_MoveFrom, m_WindowSize + m_KeepSizeAfter); + m_Pos -= m_MoveFrom; + m_StreamPos -= m_MoveFrom; +} + +}} diff --git a/hostTools/lzma/compress/WindowOut.h b/hostTools/lzma/compress/WindowOut.h new file mode 100644 index 0000000..8adad98 --- /dev/null +++ b/hostTools/lzma/compress/WindowOut.h @@ -0,0 +1,71 @@ +#ifndef __STREAM_WINDOWOUT_H +#define __STREAM_WINDOWOUT_H + +#include "IInOutStreams.h" + +namespace NStream { +namespace NWindow { + +// m_KeepSizeBefore: how mach BYTEs must be in buffer before m_Pos; +// m_KeepSizeAfter: how mach BYTEs must be in buffer after m_Pos; +// m_KeepSizeReserv: how mach BYTEs must be in buffer for Moving Reserv; +// must be >= aKeepSizeAfter; // test it + +class COut +{ + BYTE *m_Buffer; + UINT32 m_Pos; + UINT32 m_PosLimit; + UINT32 m_KeepSizeBefore; + UINT32 m_KeepSizeAfter; + UINT32 m_KeepSizeReserv; + UINT32 m_StreamPos; + + UINT32 m_WindowSize; + UINT32 m_MoveFrom; + + ISequentialOutStream *m_Stream; + + virtual void MoveBlockBackward(); +public: + COut(): m_Buffer(0), m_Stream(0) {} + virtual ~COut(); + void Create(UINT32 aKeepSizeBefore, + UINT32 aKeepSizeAfter, UINT32 aKeepSizeReserv = (1<<17)); + void SetWindowSize(UINT32 aWindowSize); + + void Init(ISequentialOutStream *aStream, bool aSolid = false); + HRESULT Flush(); + + UINT32 GetCurPos() const { return m_Pos; } + const BYTE *GetPointerToCurrentPos() const { return m_Buffer + m_Pos;}; + + void CopyBackBlock(UINT32 aDistance, UINT32 aLen) + { + if (m_Pos >= m_PosLimit) + MoveBlockBackward(); + BYTE *p = m_Buffer + m_Pos; + aDistance++; + for(UINT32 i = 0; i < aLen; i++) + p[i] = p[i - aDistance]; + m_Pos += aLen; + } + + void PutOneByte(BYTE aByte) + { + if (m_Pos >= m_PosLimit) + MoveBlockBackward(); + m_Buffer[m_Pos++] = aByte; + } + + BYTE GetOneByte(UINT32 anIndex) const + { + return m_Buffer[m_Pos + anIndex]; + } + + BYTE *GetBuffer() const { return m_Buffer; } +}; + +}} + +#endif diff --git a/hostTools/lzma/compress/lzDecomp.cpp b/hostTools/lzma/compress/lzDecomp.cpp new file mode 100644 index 0000000..f45cb4b --- /dev/null +++ b/hostTools/lzma/compress/lzDecomp.cpp @@ -0,0 +1,45 @@ +#include "stdio.h" +#include "LZMADecoder.h" + +//static LzmaDecoder cc; +ISequentialInStream in_stream; +ISequentialOutStream out_stream; +int decompress_lzma_7z( unsigned char* in_data, + unsigned in_size, + unsigned char* out_data, + unsigned out_size) { +// LzmaDecoder cc; + int RC; + UINT64 in_size_l = in_size; + UINT64 out_size_l = out_size; + + + InStreamInit(in_data, in_size); + + OutStreamInit((char *)out_data, out_size); + + LzmaDecoderConstructor(&cc); + + if ((RC = LzmaDecoderReadCoderProperties(&cc)) != S_OK) + { + return RC; + } + + if (LzmaDecoderCode(&cc, &in_size_l, &out_size_l) != S_OK) + { + return -2; + } + + if (out_stream.size != out_size) + { + return -3; + } + + if ( out_stream.overflow ) + { + return -4; + } + +printf( "\nDecompressed size: %d\n", out_stream.total ); + return 0; +} diff --git a/hostTools/lzma/decompress/7z.h b/hostTools/lzma/decompress/7z.h new file mode 100644 index 0000000..ca8ea7f --- /dev/null +++ b/hostTools/lzma/decompress/7z.h @@ -0,0 +1,16 @@ +#ifndef __7Z_H +#define __7Z_H + +#if defined __cplusplus +extern "C" +{ +#endif + +int decompress_lzma_7z(unsigned char* in_data, unsigned in_size, unsigned char* out_data, unsigned out_size); + +#if defined __cplusplus +} +#endif + +#endif + diff --git a/hostTools/lzma/decompress/7zlzma.c b/hostTools/lzma/decompress/7zlzma.c new file mode 100644 index 0000000..f45d6c2 --- /dev/null +++ b/hostTools/lzma/decompress/7zlzma.c @@ -0,0 +1,57 @@ +#include "7z.h" + +#ifdef _HOST_TOOL +#include "stdio.h" +#endif + +#include "LZMADecoder.h" + + +static LzmaDecoder cc; +ISequentialInStream in_stream; +ISequentialOutStream out_stream; +int decompress_lzma_7z( unsigned char* in_data, + unsigned in_size, + unsigned char* out_data, + unsigned out_size) { +// LzmaDecoder cc; + int RC; + UINT64 in_size_l = in_size; + UINT64 out_size_l = out_size; + + + InStreamInit(in_data, in_size); + + OutStreamInit((char *)out_data, out_size); + + LzmaDecoderConstructor(&cc); + + if ((RC = LzmaDecoderReadCoderProperties(&cc)) != S_OK) + { + return RC; + } + + if (LzmaDecoderCode(&cc, &in_size_l, &out_size_l) != S_OK) + { + return -2; + } + + if (out_stream.size != out_size) + { + return -3; + } + + if ( out_stream.overflow ) + { + return -4; + } + + return 0; +} + +//BRCM modification +#ifdef __KERNEL__ +EXPORT_SYMBOL(decompress_lzma_7z); +#endif + + diff --git a/hostTools/lzma/decompress/AriBitCoder.h b/hostTools/lzma/decompress/AriBitCoder.h new file mode 100644 index 0000000..cedc189 --- /dev/null +++ b/hostTools/lzma/decompress/AriBitCoder.h @@ -0,0 +1,51 @@ +#ifndef __COMPRESSION_BITCODER_H +#define __COMPRESSION_BITCODER_H + +#include "RangeCoder.h" + +#define kNumBitModelTotalBits 11 +#define kBitModelTotal (1 << kNumBitModelTotalBits) + +#define kNumMoveReducingBits 2 + + +typedef UINT32 CBitDecoder; + +INLINE void BitDecoderInit(CBitDecoder *bitDecoder) + { + *bitDecoder = kBitModelTotal / 2; + } + +#if 0 +UINT32 BitDecode(ISequentialInStream *in_stream, CBitDecoder *bitDecoder, CRangeDecoder *aRangeDecoder); +#else +INLINE UINT32 BitDecode(ISequentialInStream *in_stream, CBitDecoder *bitDecoder, CRangeDecoder *aRangeDecoder) + { + UINT32 aNewBound = (aRangeDecoder->m_Range >> kNumBitModelTotalBits) * (*bitDecoder); + if (aRangeDecoder->m_Code < aNewBound) + { + aRangeDecoder->m_Range = aNewBound; + *bitDecoder += (kBitModelTotal - *bitDecoder) >> kNumMoveBits; + if (aRangeDecoder->m_Range < kTopValue) + { + aRangeDecoder->m_Code = (aRangeDecoder->m_Code << 8) | InStreamReadByte(in_stream); + aRangeDecoder->m_Range <<= 8; + } + return 0; + } + else + { + aRangeDecoder->m_Range -= aNewBound; + aRangeDecoder->m_Code -= aNewBound; + *bitDecoder -= (*bitDecoder) >> kNumMoveBits; + if (aRangeDecoder->m_Range < kTopValue) + { + aRangeDecoder->m_Code = (aRangeDecoder->m_Code << 8) | InStreamReadByte(in_stream); + aRangeDecoder->m_Range <<= 8; + } + return 1; + } + } +#endif + +#endif diff --git a/hostTools/lzma/decompress/BitTreeCoder.h b/hostTools/lzma/decompress/BitTreeCoder.h new file mode 100644 index 0000000..8c663e6 --- /dev/null +++ b/hostTools/lzma/decompress/BitTreeCoder.h @@ -0,0 +1,160 @@ +#ifndef __BITTREECODER_H +#define __BITTREECODER_H + +#include "AriBitCoder.h" +#include "RCDefs.h" + +//BRCM modification start +#ifdef _HOST_TOOL +#include "stdio.h" +#include "stdlib.h" +#include "malloc.h" +#endif + +#ifdef _CFE_ +#include "lib_malloc.h" +#include "lib_printf.h" +#define malloc(x) KMALLOC(x, 0) +#endif + +#ifdef __KERNEL__ +#include +#include +#include +#define printf printk +//#define malloc(x) kmalloc(x,GFP_KERNEL) +#define malloc(x) vmalloc(x) +#define free(x) vfree(x) +#endif +//BRCM modification end + +////////////////////////// +// CBitTreeDecoder + +typedef struct CBitTreeDecoder +{ + UINT32 m_NumBitLevels; + CBitDecoder *m_Models; +} CBitTreeDecoder; + +// ~CBitTreeDecoder() { free(m_Models); } +INLINE void BitTreeDecoderInit(CBitTreeDecoder *bitTreeDecoder, UINT32 aNumBitLevels) + { + int i; + bitTreeDecoder->m_NumBitLevels = aNumBitLevels; + bitTreeDecoder->m_Models = (CBitDecoder *)malloc( sizeof(CBitDecoder) * (1 << bitTreeDecoder->m_NumBitLevels)); + //BRCM modification + //printf("malloc in BitTreeDecoderInit=%d\n",sizeof(CBitDecoder) * (1 << bitTreeDecoder->m_NumBitLevels)); + if (!bitTreeDecoder->m_Models) { + printf("Error in allocating memory for bitTreeDecoder!\n"); + return; + } + for(i = 1; i < (1 << aNumBitLevels); i++) + BitDecoderInit(&bitTreeDecoder->m_Models[i]); + } +INLINE UINT32 BitTreeDecode(ISequentialInStream *in_stream, CBitTreeDecoder *bitTreeDecoder, CRangeDecoder *aRangeDecoder) + { + UINT32 aModelIndex = 1; + UINT32 aRange = aRangeDecoder->m_Range; + UINT32 aCode = aRangeDecoder->m_Code; + UINT32 aBitIndex; + for(aBitIndex = bitTreeDecoder->m_NumBitLevels; aBitIndex > 0; aBitIndex--) + { + RC_GETBIT(kNumMoveBits, bitTreeDecoder->m_Models[aModelIndex], aModelIndex) + } + aRangeDecoder->m_Range = aRange; + aRangeDecoder->m_Code = aCode; + return aModelIndex - (1 << bitTreeDecoder->m_NumBitLevels); + } + + +//////////////////////////////// +// CReverseBitTreeDecoder2 + +typedef struct CReverseBitTreeDecoder2 +{ + UINT32 m_NumBitLevels; + CBitDecoder *m_Models; +} CReverseBitTreeDecoder2; + +// CReverseBitTreeDecoder2(): m_Models(0) { } +// ~CReverseBitTreeDecoder2() { free(m_Models); } +INLINE BOOL ReverseBitTreeDecoder2Create(CReverseBitTreeDecoder2 *reverseBitTreeDecoder2, UINT32 aNumBitLevels) + { + reverseBitTreeDecoder2->m_NumBitLevels = aNumBitLevels; + reverseBitTreeDecoder2->m_Models = (CBitDecoder *)malloc( sizeof(CBitDecoder) * (1 << reverseBitTreeDecoder2->m_NumBitLevels)); + //printf("malloc in ReverseBitTreeDecoder2Create=%d\n",sizeof(CBitDecoder) * (1 << reverseBitTreeDecoder2->m_NumBitLevels)); + if (!reverseBitTreeDecoder2->m_Models) { + printf("Error in allocating memory for reverseBitTreeDecoder2!\n"); + return 0; + } + return (reverseBitTreeDecoder2->m_Models != 0); + } +INLINE void ReverseBitTreeDecoder2Init(CReverseBitTreeDecoder2 *reverseBitTreeDecoder2) + { + UINT32 aNumModels = 1 << reverseBitTreeDecoder2->m_NumBitLevels; + UINT32 i; + for(i = 1; i < aNumModels; i++) + BitDecoderInit(&reverseBitTreeDecoder2->m_Models[i]); + } +INLINE UINT32 ReverseBitTreeDecoder2Decode(ISequentialInStream *in_stream, CReverseBitTreeDecoder2 *reverseBitTreeDecoder2, CRangeDecoder *aRangeDecoder) + { + UINT32 aModelIndex = 1; + UINT32 aSymbol = 0; + UINT32 aRange = aRangeDecoder->m_Range; + UINT32 aCode = aRangeDecoder->m_Code; + UINT32 aBitIndex; + for(aBitIndex = 0; aBitIndex < reverseBitTreeDecoder2->m_NumBitLevels; aBitIndex++) + { + RC_GETBIT2(kNumMoveBits, reverseBitTreeDecoder2->m_Models[aModelIndex], aModelIndex, ; , aSymbol |= (1 << aBitIndex)) + } + aRangeDecoder->m_Range = aRange; + aRangeDecoder->m_Code = aCode; + return aSymbol; + } + + +//////////////////////////// +// CReverseBitTreeDecoder + +typedef struct CReverseBitTreeDecoder +{ + UINT32 m_NumBitLevels; + CBitDecoder *m_Models; +} CReverseBitTreeDecoder; + +// CReverseBitTreeDecoder(): m_Models(0) { } +// ~CReverseBitTreeDecoder() { free(m_Models); } +INLINE void ReverseBitTreeDecoderInit(CReverseBitTreeDecoder *reverseBitTreeDecoder, UINT32 aNumBitLevels) + { + int i; + reverseBitTreeDecoder->m_NumBitLevels = aNumBitLevels; + reverseBitTreeDecoder->m_Models = (CBitDecoder *)malloc( sizeof(CBitDecoder) * (1 << reverseBitTreeDecoder->m_NumBitLevels)); + //printf("malloc in ReverseBitTreeDecoderInit=%d\n",sizeof(CBitDecoder) * (1 << reverseBitTreeDecoder->m_NumBitLevels)); + if (!reverseBitTreeDecoder->m_Models) { + printf("Error in allocating memory for reverseBitTreeDecoder!\n"); + return; + } + for(i = 1; i < (1 << reverseBitTreeDecoder->m_NumBitLevels); i++) + BitDecoderInit(&reverseBitTreeDecoder->m_Models[i]); + } + +INLINE UINT32 ReverseBitTreeDecoderDecode(ISequentialInStream *in_stream, CReverseBitTreeDecoder *reverseBitTreeDecoder, CRangeDecoder *aRangeDecoder) + { + UINT32 aModelIndex = 1; + UINT32 aSymbol = 0; + UINT32 aRange = aRangeDecoder->m_Range; + UINT32 aCode = aRangeDecoder->m_Code; + UINT32 aBitIndex; + for(aBitIndex = 0; aBitIndex < reverseBitTreeDecoder->m_NumBitLevels; aBitIndex++) + { + RC_GETBIT2(kNumMoveBits, reverseBitTreeDecoder->m_Models[aModelIndex], aModelIndex, ; , aSymbol |= (1 << aBitIndex)) + } + aRangeDecoder->m_Range = aRange; + aRangeDecoder->m_Code = aCode; + return aSymbol; + } + + + +#endif diff --git a/hostTools/lzma/decompress/IInOutStreams.c b/hostTools/lzma/decompress/IInOutStreams.c new file mode 100644 index 0000000..789c4ae --- /dev/null +++ b/hostTools/lzma/decompress/IInOutStreams.c @@ -0,0 +1,38 @@ +#include "IInOutStreams.h" +// BRCM modification +static void *lib_memcpy(void *dest,const void *src,size_t cnt); +static void *lib_memcpy(void *dest,const void *src,size_t cnt) +{ + unsigned char *d; + const unsigned char *s; + + d = (unsigned char *) dest; + s = (const unsigned char *) src; + + while (cnt) { + *d++ = *s++; + cnt--; + } + + return dest; +} + +HRESULT InStreamRead(void *aData, UINT32 aSize, UINT32* aProcessedSize) { + if (aSize > in_stream.remainingBytes) + aSize = in_stream.remainingBytes; + *aProcessedSize = aSize; + lib_memcpy(aData, in_stream.data, aSize); // brcm modification + in_stream.remainingBytes -= aSize; + in_stream.data += aSize; + return S_OK; + } + +#if 0 +BYTE InStreamReadByte() + { + if (in_stream.remainingBytes == 0) + return 0x0; + in_stream.remainingBytes--; + return (BYTE) *in_stream.data++; + } +#endif diff --git a/hostTools/lzma/decompress/IInOutStreams.h b/hostTools/lzma/decompress/IInOutStreams.h new file mode 100644 index 0000000..69abf39 --- /dev/null +++ b/hostTools/lzma/decompress/IInOutStreams.h @@ -0,0 +1,62 @@ +#ifndef __IINOUTSTREAMS_H +#define __IINOUTSTREAMS_H + +#include "Portable.h" + +typedef struct ISequentialInStream +{ + unsigned char* data; + unsigned remainingBytes; +} ISequentialInStream; + +extern ISequentialInStream in_stream; + +INLINE void InStreamInit(unsigned char * Adata, unsigned Asize) + { + in_stream.data = Adata; + in_stream.remainingBytes = Asize; + } + +HRESULT InStreamRead(void *aData, UINT32 aSize, UINT32* aProcessedSize); + +#if 0 +BYTE InStreamReadByte(); +#else +INLINE BYTE InStreamReadByte(ISequentialInStream *in_stream) + { + if (in_stream->remainingBytes == 0) + return 0x0; + in_stream->remainingBytes--; + return (BYTE) *in_stream->data++; + } +#endif + + + +typedef struct ISequentialOutStream +{ + char* data; + unsigned size; + BOOL overflow; + unsigned total; +} ISequentialOutStream; + +extern ISequentialOutStream out_stream; + +#define OutStreamInit(Adata, Asize) \ +{ \ + out_stream.data = Adata; \ + out_stream.size = Asize; \ + out_stream.overflow = FALSE; \ + out_stream.total = 0; \ +} + +#define OutStreamSizeSet(newsize) \ + { \ + out_stream.total = newsize; \ + if (out_stream.total > out_stream.size) \ + out_stream.overflow = TRUE; \ + } + + +#endif diff --git a/hostTools/lzma/decompress/LZMA.h b/hostTools/lzma/decompress/LZMA.h new file mode 100644 index 0000000..368328c --- /dev/null +++ b/hostTools/lzma/decompress/LZMA.h @@ -0,0 +1,83 @@ +#include "LenCoder.h" + +#ifndef __LZMA_H +#define __LZMA_H + + +#define kNumRepDistances 4 + +#define kNumStates 12 + +static const BYTE kLiteralNextStates[kNumStates] = {0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5}; +static const BYTE kMatchNextStates[kNumStates] = {7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10}; +static const BYTE kRepNextStates[kNumStates] = {8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11}; +static const BYTE kShortRepNextStates[kNumStates]= {9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11}; + +typedef BYTE CState; + +INLINE void CStateInit(CState *m_Index) + { *m_Index = 0; } +INLINE void CStateUpdateChar(CState *m_Index) + { *m_Index = kLiteralNextStates[*m_Index]; } +INLINE void CStateUpdateMatch(CState *m_Index) + { *m_Index = kMatchNextStates[*m_Index]; } +INLINE void CStateUpdateRep(CState *m_Index) + { *m_Index = kRepNextStates[*m_Index]; } +INLINE void CStateUpdateShortRep(CState *m_Index) + { *m_Index = kShortRepNextStates[*m_Index]; } + + +#define kNumPosSlotBits 6 +#define kDicLogSizeMax 28 +#define kDistTableSizeMax 56 + +//extern UINT32 kDistStart[kDistTableSizeMax]; +static const BYTE kDistDirectBits[kDistTableSizeMax] = +{ + 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, + 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, + 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26 +}; + +#define kNumLenToPosStates 4 +INLINE UINT32 GetLenToPosState(UINT32 aLen) +{ + aLen -= 2; + if (aLen < kNumLenToPosStates) + return aLen; + return kNumLenToPosStates - 1; +} + +#define kMatchMinLen 2 + +#define kMatchMaxLen (kMatchMinLen + kNumSymbolsTotal - 1) + +#define kNumAlignBits 4 +#define kAlignTableSize 16 +#define kAlignMask 15 + +#define kStartPosModelIndex 4 +#define kEndPosModelIndex 14 +#define kNumPosModels 10 + +#define kNumFullDistances (1 << (kEndPosModelIndex / 2)) + + +#define kMainChoiceLiteralIndex 0 +#define kMainChoiceMatchIndex 1 + +#define kMatchChoiceDistanceIndex0 +#define kMatchChoiceRepetitionIndex 1 + +#define kNumMoveBitsForMainChoice 5 +#define kNumMoveBitsForPosCoders 5 + +#define kNumMoveBitsForAlignCoders 5 + +#define kNumMoveBitsForPosSlotCoder 5 + +#define kNumLitPosStatesBitsEncodingMax 4 +#define kNumLitContextBitsMax 8 + + +#endif diff --git a/hostTools/lzma/decompress/LZMADecoder.c b/hostTools/lzma/decompress/LZMADecoder.c new file mode 100644 index 0000000..fe6d86d --- /dev/null +++ b/hostTools/lzma/decompress/LZMADecoder.c @@ -0,0 +1,398 @@ +#include "Portable.h" +#ifdef _HOST_TOOL +#include "stdio.h" +#endif +#include "LZMADecoder.h" + + +//#define RETURN_E_OUTOFMEMORY_IF_FALSE(x) { if (!(x)) return E_OUTOFMEMORY; } + + +static UINT32 kDistStart[kDistTableSizeMax]; +struct WindowOut out_window; + +/* + * BRCM modification: free all the allocated buffer by malloc + * + */ +static void LzmaDecoderFreeBuffer(LzmaDecoder *lzmaDecoder) +{ + int i,aPosState; + + //printf("free lzmaDecoder->m_LiteralDecoder\n"); + free((&lzmaDecoder->m_LiteralDecoder)->m_Coders); + + for (i = 0; i < kNumLenToPosStates; i++) { + //printf("free lzmaDecoder->m_PosSlotDecoder\n"); + free((&lzmaDecoder->m_PosSlotDecoder[i])->m_Models); + } + // from LenDecoderInit(&lzmaDecoder->m_LenDecoder; + for (aPosState = 0; aPosState < (&lzmaDecoder->m_LenDecoder)->m_NumPosStates; aPosState++) { + //printf("free lzmaDecoder->m_PosSlotDecoder\n"); + free( (&(&lzmaDecoder->m_LenDecoder)->m_LowCoder[aPosState])->m_Models ); + //printf("free lzmaDecoder->m_PosSlotDecoder\n"); + free( (&(&lzmaDecoder->m_LenDecoder)->m_MidCoder[aPosState])->m_Models ); + } + //printf("free lzmaDecoder->m_PosSlotDecoder\n"); + free( (&(&lzmaDecoder->m_LenDecoder)->m_HighCoder)->m_Models ); + + + // from LenDecoderInit(&lzmaDecoder->m_RepMatchLenDecoder); + for (aPosState = 0; aPosState < (&lzmaDecoder->m_RepMatchLenDecoder)->m_NumPosStates; aPosState++) { + //printf("free lzmaDecoder->m_PosSlotDecoder\n"); + free( (&(&lzmaDecoder->m_RepMatchLenDecoder)->m_LowCoder[aPosState])->m_Models ); + //printf("free lzmaDecoder->m_PosSlotDecoder\n"); + free( (&(&lzmaDecoder->m_RepMatchLenDecoder)->m_MidCoder[aPosState])->m_Models ); + } + //printf("free lzmaDecoder->m_PosSlotDecoder\n"); + free( (&(&lzmaDecoder->m_RepMatchLenDecoder)->m_HighCoder)->m_Models ); + + + //printf("free lzmaDecoder->m_PosAlignDecoder\n"); + free((&lzmaDecoder->m_PosAlignDecoder)->m_Models); + + for(i = 0; i < kNumPosModels; i++) { + //printf("free lzmaDecoder->m_PosDecoders\n"); + free((&lzmaDecoder->m_PosDecoders[i])->m_Models); + } + +} + +HRESULT LzmaDecoderSetDictionarySize( + LzmaDecoder *lzmaDecoder, + UINT32 aDictionarySize) +{ + if (aDictionarySize > (1 << kDicLogSizeMax)) + return E_INVALIDARG; + +// UINT32 aWindowReservSize = MyMax(aDictionarySize, UINT32(1 << 21)); + + if (lzmaDecoder->m_DictionarySize != aDictionarySize) + { + lzmaDecoder->m_DictionarySize = aDictionarySize; + } + return S_OK; +} + +HRESULT LzmaDecoderSetLiteralProperties( + LzmaDecoder *lzmaDecoder, + UINT32 aLiteralPosStateBits, + UINT32 aLiteralContextBits) +{ + if (aLiteralPosStateBits > 8) + return E_INVALIDARG; + if (aLiteralContextBits > 8) + return E_INVALIDARG; + LitDecoderCreate(&lzmaDecoder->m_LiteralDecoder, aLiteralPosStateBits, aLiteralContextBits); + return S_OK; +} + +HRESULT LzmaDecoderSetPosBitsProperties( + LzmaDecoder *lzmaDecoder, + UINT32 aNumPosStateBits) +{ + UINT32 aNumPosStates; + if (aNumPosStateBits > (UINT32) kNumPosStatesBitsMax) + return E_INVALIDARG; + aNumPosStates = 1 << aNumPosStateBits; + LenDecoderCreate(&lzmaDecoder->m_LenDecoder, aNumPosStates); + LenDecoderCreate(&lzmaDecoder->m_RepMatchLenDecoder, aNumPosStates); + lzmaDecoder->m_PosStateMask = aNumPosStates - 1; + return S_OK; +} + + +void LzmaDecoderConstructor(LzmaDecoder *lzmaDecoder) +{ + lzmaDecoder->m_DictionarySize = ((UINT32)-1); + LzmaDecoderCreate(lzmaDecoder); +} + +HRESULT LzmaDecoderCreate(LzmaDecoder *lzmaDecoder) +{ + int i; + for(i = 0; i < kNumPosModels; i++) + { + if (!(ReverseBitTreeDecoder2Create(&lzmaDecoder->m_PosDecoders[i],kDistDirectBits[kStartPosModelIndex + i]))) + return E_OUTOFMEMORY;; + } + return S_OK; +} + + +HRESULT LzmaDecoderInit(LzmaDecoder *lzmaDecoder) +{ + int i; + UINT32 j; + + RangeDecoderInit(&in_stream, &lzmaDecoder->m_RangeDecoder); + + OutWindowInit(); + + for(i = 0; i < kNumStates; i++) + { + for (j = 0; j <= lzmaDecoder->m_PosStateMask; j++) + { + BitDecoderInit(&lzmaDecoder->m_MainChoiceDecoders[i][j]); + BitDecoderInit(&lzmaDecoder->m_MatchRepShortChoiceDecoders[i][j]); + } + BitDecoderInit(&lzmaDecoder->m_MatchChoiceDecoders[i]); + BitDecoderInit(&lzmaDecoder->m_MatchRepChoiceDecoders[i]); + BitDecoderInit(&lzmaDecoder->m_MatchRep1ChoiceDecoders[i]); + BitDecoderInit(&lzmaDecoder->m_MatchRep2ChoiceDecoders[i]); + } + + LitDecoderInit(&lzmaDecoder->m_LiteralDecoder); + + for (i = 0; i < (int) kNumLenToPosStates; i++) + BitTreeDecoderInit(&lzmaDecoder->m_PosSlotDecoder[i],kNumPosSlotBits); + + for(i = 0; i < kNumPosModels; i++) + ReverseBitTreeDecoder2Init(&lzmaDecoder->m_PosDecoders[i]); + + LenDecoderInit(&lzmaDecoder->m_LenDecoder); + LenDecoderInit(&lzmaDecoder->m_RepMatchLenDecoder); + + ReverseBitTreeDecoderInit(&lzmaDecoder->m_PosAlignDecoder, kNumAlignBits); + return S_OK; + +} + +HRESULT LzmaDecoderCodeReal( + LzmaDecoder *lzmaDecoder, + UINT64 *anInSize, + UINT64 *anOutSize) +{ + BOOL aPeviousIsMatch = FALSE; + BYTE aPreviousByte = 0; + UINT32 aRepDistances[kNumRepDistances]; + int i; + UINT64 aNowPos64 = 0; + UINT64 aSize = *anOutSize; + ISequentialInStream my_in_stream; +// WindowOut out_window; + CState aState; + + CStateInit(&aState); + + if (anOutSize == NULL) + { + printf("CodeReal: invalid argument %x\n", (UINT32) anOutSize ); + return E_INVALIDARG; + } + + + LzmaDecoderInit(lzmaDecoder); + + my_in_stream.data = in_stream.data; + my_in_stream.remainingBytes = in_stream.remainingBytes; + + for(i = 0 ; i < (int) kNumRepDistances; i++) + aRepDistances[i] = 0; + + //while(aNowPos64 < aSize) + while(my_in_stream.remainingBytes > 0) + { + UINT64 aNext = MyMin(aNowPos64 + (1 << 18), aSize); + while(aNowPos64 < aNext) + { + UINT32 aPosState = (UINT32)(aNowPos64) & lzmaDecoder->m_PosStateMask; + if (BitDecode(&my_in_stream, + &lzmaDecoder->m_MainChoiceDecoders[aState][aPosState], + &lzmaDecoder->m_RangeDecoder) == (UINT32) kMainChoiceLiteralIndex) + { + CStateUpdateChar(&aState); + if(aPeviousIsMatch) + { + BYTE aMatchByte = OutWindowGetOneByte(0 - aRepDistances[0] - 1); + aPreviousByte = LitDecodeWithMatchByte(&my_in_stream, + &lzmaDecoder->m_LiteralDecoder, + &lzmaDecoder->m_RangeDecoder, + (UINT32)(aNowPos64), + aPreviousByte, + aMatchByte); + aPeviousIsMatch = FALSE; + } + else + aPreviousByte = LitDecodeNormal(&my_in_stream, + &lzmaDecoder->m_LiteralDecoder, + &lzmaDecoder->m_RangeDecoder, + (UINT32)(aNowPos64), + aPreviousByte); + OutWindowPutOneByte(aPreviousByte); + aNowPos64++; + } + else + { + UINT32 aDistance, aLen; + aPeviousIsMatch = TRUE; + if(BitDecode(&my_in_stream, + &lzmaDecoder->m_MatchChoiceDecoders[aState], + &lzmaDecoder->m_RangeDecoder) == (UINT32) kMatchChoiceRepetitionIndex) + { + if(BitDecode(&my_in_stream, + &lzmaDecoder->m_MatchRepChoiceDecoders[aState], + &lzmaDecoder->m_RangeDecoder) == 0) + { + if(BitDecode(&my_in_stream, + &lzmaDecoder->m_MatchRepShortChoiceDecoders[aState][aPosState], + &lzmaDecoder->m_RangeDecoder) == 0) + { + CStateUpdateShortRep(&aState); + aPreviousByte = OutWindowGetOneByte(0 - aRepDistances[0] - 1); + OutWindowPutOneByte(aPreviousByte); + aNowPos64++; + continue; + } + aDistance = aRepDistances[0]; + } + else + { + if(BitDecode(&my_in_stream, + &lzmaDecoder->m_MatchRep1ChoiceDecoders[aState], + &lzmaDecoder->m_RangeDecoder) == 0) + { + aDistance = aRepDistances[1]; + aRepDistances[1] = aRepDistances[0]; + } + else + { + if (BitDecode(&my_in_stream, + &lzmaDecoder->m_MatchRep2ChoiceDecoders[aState], + &lzmaDecoder->m_RangeDecoder) == 0) + { + aDistance = aRepDistances[2]; + } + else + { + aDistance = aRepDistances[3]; + aRepDistances[3] = aRepDistances[2]; + } + aRepDistances[2] = aRepDistances[1]; + aRepDistances[1] = aRepDistances[0]; + } + aRepDistances[0] = aDistance; + } + aLen = LenDecode(&my_in_stream, + &lzmaDecoder->m_RepMatchLenDecoder, + &lzmaDecoder->m_RangeDecoder, + aPosState) + kMatchMinLen; + CStateUpdateRep(&aState); + } + else + { + UINT32 aPosSlot; + aLen = kMatchMinLen + LenDecode(&my_in_stream, + &lzmaDecoder->m_LenDecoder, + &lzmaDecoder->m_RangeDecoder, + aPosState); + CStateUpdateMatch(&aState); + aPosSlot = BitTreeDecode(&my_in_stream, + &lzmaDecoder->m_PosSlotDecoder[GetLenToPosState(aLen)], + &lzmaDecoder->m_RangeDecoder); + if (aPosSlot >= (UINT32) kStartPosModelIndex) + { + aDistance = kDistStart[aPosSlot]; + if (aPosSlot < (UINT32) kEndPosModelIndex) + aDistance += ReverseBitTreeDecoder2Decode(&my_in_stream, + &lzmaDecoder->m_PosDecoders[aPosSlot - kStartPosModelIndex], + &lzmaDecoder->m_RangeDecoder); + else + { + aDistance += (RangeDecodeDirectBits(&my_in_stream, + &lzmaDecoder->m_RangeDecoder, + kDistDirectBits[aPosSlot] - kNumAlignBits) << kNumAlignBits); + aDistance += ReverseBitTreeDecoderDecode(&my_in_stream, + &lzmaDecoder->m_PosAlignDecoder, + &lzmaDecoder->m_RangeDecoder); + } + } + else + aDistance = aPosSlot; + + + aRepDistances[3] = aRepDistances[2]; + aRepDistances[2] = aRepDistances[1]; + aRepDistances[1] = aRepDistances[0]; + + aRepDistances[0] = aDistance; + } + if (aDistance >= aNowPos64) + { + printf("CodeReal: invalid data\n" ); + return E_INVALIDDATA; + } + OutWindowCopyBackBlock(aDistance, aLen); + aNowPos64 += aLen; + aPreviousByte = OutWindowGetOneByte(0 - 1); + } + } + } + + //BRCM modification + LzmaDecoderFreeBuffer(lzmaDecoder); + + OutWindowFlush(); + return S_OK; +} + +HRESULT LzmaDecoderCode( + LzmaDecoder *lzmaDecoder, + UINT64 *anInSize, + UINT64 *anOutSize) +{ + + UINT32 aStartValue = 0; + int i; + + for (i = 0; i < kDistTableSizeMax; i++) + { + kDistStart[i] = aStartValue; + aStartValue += (1 << kDistDirectBits[i]); + } + return LzmaDecoderCodeReal( + lzmaDecoder, + anInSize, + anOutSize); +} + +HRESULT LzmaDecoderReadCoderProperties(LzmaDecoder *lzmaDecoder) +{ + UINT32 aNumPosStateBits; + UINT32 aLiteralPosStateBits; + UINT32 aLiteralContextBits; + UINT32 aDictionarySize; + BYTE aRemainder; + UINT32 aProcessesedSize; + + BYTE aByte; + RETURN_IF_NOT_S_OK(InStreamRead(&aByte, + sizeof(aByte), + &aProcessesedSize)); + + if (aProcessesedSize != sizeof(aByte)) + return E_INVALIDARG; + + aLiteralContextBits = aByte % 9; + aRemainder = aByte / 9; + aLiteralPosStateBits = aRemainder % 5; + aNumPosStateBits = aRemainder / 5; + + RETURN_IF_NOT_S_OK(InStreamRead(&aDictionarySize, + sizeof(aDictionarySize), + &aProcessesedSize)); + + if (aProcessesedSize != sizeof(aDictionarySize)) + return E_INVALIDARG; + + RETURN_IF_NOT_S_OK( LzmaDecoderSetDictionarySize(lzmaDecoder, + aDictionarySize) ); + RETURN_IF_NOT_S_OK( LzmaDecoderSetLiteralProperties(lzmaDecoder, + aLiteralPosStateBits, + aLiteralContextBits) ); + RETURN_IF_NOT_S_OK( LzmaDecoderSetPosBitsProperties(lzmaDecoder, + aNumPosStateBits) ); + + return S_OK; +} + diff --git a/hostTools/lzma/decompress/LZMADecoder.h b/hostTools/lzma/decompress/LZMADecoder.h new file mode 100644 index 0000000..76fa536 --- /dev/null +++ b/hostTools/lzma/decompress/LZMADecoder.h @@ -0,0 +1,60 @@ +#ifndef __LZARITHMETIC_DECODER_H +#define __LZARITHMETIC_DECODER_H + +#include "WindowOut.h" +#include "LZMA.h" +#include "LenCoder.h" +#include "LiteralCoder.h" + + +typedef struct LzmaDecoder +{ + CRangeDecoder m_RangeDecoder; + + CBitDecoder m_MainChoiceDecoders[kNumStates][kNumPosStatesMax]; + CBitDecoder m_MatchChoiceDecoders[kNumStates]; + CBitDecoder m_MatchRepChoiceDecoders[kNumStates]; + CBitDecoder m_MatchRep1ChoiceDecoders[kNumStates]; + CBitDecoder m_MatchRep2ChoiceDecoders[kNumStates]; + CBitDecoder m_MatchRepShortChoiceDecoders[kNumStates][kNumPosStatesMax]; + + CBitTreeDecoder m_PosSlotDecoder[kNumLenToPosStates]; + + CReverseBitTreeDecoder2 m_PosDecoders[kNumPosModels]; + CReverseBitTreeDecoder m_PosAlignDecoder; + + LenDecoder m_LenDecoder; + LenDecoder m_RepMatchLenDecoder; + + LitDecoder m_LiteralDecoder; + + UINT32 m_DictionarySize; + + UINT32 m_PosStateMask; +} LzmaDecoder; + + HRESULT LzmaDecoderCreate(LzmaDecoder *lzmaDecoder); + + HRESULT LzmaDecoderInit(LzmaDecoder *lzmaDecoder); + +//static inline HRESULT LzmaDecoderFlush() { return OutWindowFlush(); } + + HRESULT LzmaDecoderCodeReal( + LzmaDecoder *lzmaDecoder, +// ISequentialInStream *in_stream, + UINT64 *anInSize, +// WindowOut *out_window, + UINT64 *anOutSize); + + + void LzmaDecoderConstructor( LzmaDecoder *lzmaDecoder ); + + HRESULT LzmaDecoderCode( LzmaDecoder *lzmaDecoder, UINT64 *anInSize, UINT64 *anOutSize); + HRESULT LzmaDecoderReadCoderProperties(LzmaDecoder *lzmaDecoder ); + + HRESULT LzmaDecoderSetDictionarySize(LzmaDecoder *lzmaDecoder, UINT32 aDictionarySize); + HRESULT LzmaDecoderSetLiteralProperties(LzmaDecoder *lzmaDecoder, UINT32 aLiteralPosStateBits, UINT32 aLiteralContextBits); + HRESULT LzmaDecoderSetPosBitsProperties(LzmaDecoder *lzmaDecoder, UINT32 aNumPosStateBits); + + +#endif diff --git a/hostTools/lzma/decompress/LenCoder.h b/hostTools/lzma/decompress/LenCoder.h new file mode 100644 index 0000000..40552b8 --- /dev/null +++ b/hostTools/lzma/decompress/LenCoder.h @@ -0,0 +1,75 @@ +#ifndef __LENCODER_H +#define __LENCODER_H + +#include "BitTreeCoder.h" + + +#define kNumPosStatesBitsMax 4 +#define kNumPosStatesMax 16 + + +#define kNumPosStatesBitsEncodingMax 4 +#define kNumPosStatesEncodingMax 16 + + +//#define kNumMoveBits 5 + +#define kNumLenBits 3 +#define kNumLowSymbols (1 << kNumLenBits) + +#define kNumMidBits 3 +#define kNumMidSymbols (1 << kNumMidBits) + +#define kNumHighBits 8 + +#define kNumSymbolsTotal (kNumLowSymbols + kNumMidSymbols + (1 << kNumHighBits)) + +typedef struct LenDecoder +{ + CBitDecoder m_Choice; + CBitDecoder m_Choice2; + CBitTreeDecoder m_LowCoder[kNumPosStatesMax]; + CBitTreeDecoder m_MidCoder[kNumPosStatesMax]; + CBitTreeDecoder m_HighCoder; + UINT32 m_NumPosStates; +} LenDecoder; + +INLINE void LenDecoderCreate(LenDecoder *lenCoder, UINT32 aNumPosStates) + { + lenCoder->m_NumPosStates = aNumPosStates; + } + +INLINE void LenDecoderInit(LenDecoder *lenCoder) + { + UINT32 aPosState; + BitDecoderInit(&lenCoder->m_Choice); + for (aPosState = 0; aPosState < lenCoder->m_NumPosStates; aPosState++) + { + BitTreeDecoderInit(&lenCoder->m_LowCoder[aPosState],kNumLenBits); + BitTreeDecoderInit(&lenCoder->m_MidCoder[aPosState],kNumMidBits); + } + BitTreeDecoderInit(&lenCoder->m_HighCoder,kNumHighBits); + BitDecoderInit(&lenCoder->m_Choice2); + } + +INLINE UINT32 LenDecode(ISequentialInStream *in_stream, LenDecoder *lenCoder, CRangeDecoder *aRangeDecoder, UINT32 aPosState) + { + if(BitDecode(in_stream, &lenCoder->m_Choice, aRangeDecoder) == 0) + return BitTreeDecode(in_stream, &lenCoder->m_LowCoder[aPosState],aRangeDecoder); + else + { + UINT32 aSymbol = kNumLowSymbols; + if(BitDecode(in_stream, &lenCoder->m_Choice2, aRangeDecoder) == 0) + aSymbol += BitTreeDecode(in_stream, &lenCoder->m_MidCoder[aPosState],aRangeDecoder); + else + { + aSymbol += kNumMidSymbols; + aSymbol += BitTreeDecode(in_stream, &lenCoder->m_HighCoder,aRangeDecoder); + } + return aSymbol; + } + } + + + +#endif diff --git a/hostTools/lzma/decompress/LiteralCoder.h b/hostTools/lzma/decompress/LiteralCoder.h new file mode 100644 index 0000000..2b1670d --- /dev/null +++ b/hostTools/lzma/decompress/LiteralCoder.h @@ -0,0 +1,146 @@ +#ifndef __LITERALCODER_H +#define __LITERALCODER_H + +#include "AriBitCoder.h" +#include "RCDefs.h" + +//BRCM modification start +#ifdef _HOST_TOOL +#include "stdio.h" +#include "malloc.h" +#endif + +#ifdef _CFE_ +#include "lib_malloc.h" +#include "lib_printf.h" +#define malloc(x) KMALLOC(x, 0) +#define free(x) KFREE(x) +#endif + +#ifdef __KERNEL__ +#include +#include +#define printf printk +//#define malloc(x) kmalloc(x,GFP_KERNEL) +#define malloc(x) vmalloc(x) +#define free(x) vfree(x) +#endif +//BRCM modification end + +//#define kNumMoveBits 5 + +typedef struct LitDecoder2 +{ + CBitDecoder m_Decoders[3][1 << 8]; +} LitDecoder2; + + +INLINE void LitDecoder2Init(LitDecoder2 *litDecoder2) + { + int i, j; + for (i = 0; i < 3; i++) + for (j = 1; j < (1 << 8); j++) + BitDecoderInit(&litDecoder2->m_Decoders[i][j]); + } + +INLINE BYTE LitDecoder2DecodeNormal(ISequentialInStream *in_stream, LitDecoder2 *litDecoder2, CRangeDecoder *aRangeDecoder) + { + UINT32 aSymbol = 1; + UINT32 aRange = aRangeDecoder->m_Range; + UINT32 aCode = aRangeDecoder->m_Code; + do + { + RC_GETBIT(kNumMoveBits, litDecoder2->m_Decoders[0][aSymbol], aSymbol) + } + while (aSymbol < 0x100); + aRangeDecoder->m_Range = aRange; + aRangeDecoder->m_Code = aCode; + return aSymbol; + } + +INLINE BYTE LitDecoder2DecodeWithMatchByte(ISequentialInStream *in_stream, LitDecoder2 *litDecoder2, CRangeDecoder *aRangeDecoder, BYTE aMatchByte) + { + UINT32 aSymbol = 1; + UINT32 aRange = aRangeDecoder->m_Range; + UINT32 aCode = aRangeDecoder->m_Code; + do + { + UINT32 aBit; + UINT32 aMatchBit = (aMatchByte >> 7) & 1; + aMatchByte <<= 1; + RC_GETBIT2(kNumMoveBits, litDecoder2->m_Decoders[1 + aMatchBit][aSymbol], aSymbol, + aBit = 0, aBit = 1) + if (aMatchBit != aBit) + { + while (aSymbol < 0x100) + { + RC_GETBIT(kNumMoveBits, litDecoder2->m_Decoders[0][aSymbol], aSymbol) + } + break; + } + } + while (aSymbol < 0x100); + aRangeDecoder->m_Range = aRange; + aRangeDecoder->m_Code = aCode; + return aSymbol; + } + + +typedef struct LitDecoder +{ + LitDecoder2 *m_Coders; + UINT32 m_NumPrevBits; + UINT32 m_NumPosBits; + UINT32 m_PosMask; +} LitDecoder; + + +// LitDecoder(): m_Coders(0) {} +// ~LitDecoder() { Free(); } + +/* +INLINE void LitDecoderFree(LitDecoder *litDecoder) + { + free( (char *) litDecoder->m_Coders ); + litDecoder->m_Coders = 0; + } +*/ + +INLINE void LitDecoderCreate(LitDecoder *litDecoder, UINT32 aNumPosBits, UINT32 aNumPrevBits) + { +// LitDecoderFree(litDecoder); + UINT32 aNumStates; + litDecoder->m_NumPosBits = aNumPosBits; + litDecoder->m_PosMask = (1 << aNumPosBits) - 1; + litDecoder->m_NumPrevBits = aNumPrevBits; + aNumStates = 1 << (aNumPrevBits + aNumPosBits); + litDecoder->m_Coders = (LitDecoder2*) malloc( sizeof( LitDecoder2 ) * aNumStates ); + //printf("malloc in LitDecoderCreate=%d\n",sizeof( LitDecoder2 ) * aNumStates); + if (litDecoder->m_Coders == 0) + printf( "Error allocating memory for LitDecoder m_Coders!\n" ); + } + +INLINE void LitDecoderInit(LitDecoder *litDecoder) + { + UINT32 i; + UINT32 aNumStates = 1 << (litDecoder->m_NumPrevBits + litDecoder->m_NumPosBits); + for (i = 0; i < aNumStates; i++) + LitDecoder2Init(&litDecoder->m_Coders[i]); + } + +INLINE UINT32 LitDecoderGetState(LitDecoder *litDecoder, UINT32 aPos, BYTE aPrevByte) + { + return ((aPos & litDecoder->m_PosMask) << litDecoder->m_NumPrevBits) + (aPrevByte >> (8 - litDecoder->m_NumPrevBits)); + } + +INLINE BYTE LitDecodeNormal(ISequentialInStream *in_stream, LitDecoder *litDecoder, CRangeDecoder *aRangeDecoder, UINT32 aPos, BYTE aPrevByte) + { + return LitDecoder2DecodeNormal(in_stream, &litDecoder->m_Coders[LitDecoderGetState(litDecoder, aPos, aPrevByte)], aRangeDecoder); + } + +INLINE BYTE LitDecodeWithMatchByte(ISequentialInStream *in_stream, LitDecoder *litDecoder, CRangeDecoder *aRangeDecoder, UINT32 aPos, BYTE aPrevByte, BYTE aMatchByte) + { + return LitDecoder2DecodeWithMatchByte(in_stream, &litDecoder->m_Coders[LitDecoderGetState(litDecoder, aPos, aPrevByte)], aRangeDecoder, aMatchByte); + } + +#endif diff --git a/hostTools/lzma/decompress/Makefile b/hostTools/lzma/decompress/Makefile new file mode 100644 index 0000000..e21ff1d --- /dev/null +++ b/hostTools/lzma/decompress/Makefile @@ -0,0 +1,6 @@ + +BSPOBJS += \ + 7zlzma.o \ + LZMADecoder.o \ + IInOutStreams.o \ + diff --git a/hostTools/lzma/decompress/Portable.h b/hostTools/lzma/decompress/Portable.h new file mode 100644 index 0000000..698f30b --- /dev/null +++ b/hostTools/lzma/decompress/Portable.h @@ -0,0 +1,59 @@ +#ifndef __PORTABLE_H +#define __PORTABLE_H + +//BRCM modification +#ifdef _HOST_TOOL +#include +#endif + +#ifdef _CFE_ +#include +#endif + +#ifdef __KERNEL__ +#include +#endif + +//bcm +//#ifdef __GNUC__ +//#include +//#define INLINE static inline +//#else +typedef char INT8; +typedef unsigned char UINT8; +typedef short INT16; +typedef unsigned short UINT16; +typedef int INT32; +typedef unsigned int UINT32; +typedef int BOOL; +#define INLINE static inline +//#define INLINE static __inline__ +//#endif +typedef long long INT64; // %%%% Changed from "long long" +typedef unsigned long long UINT64; // %%%% Changed from "long long" + +typedef UINT8 BYTE; +typedef UINT16 WORD; +typedef UINT32 DWORD; + +typedef unsigned UINT_PTR; +#define FALSE 0 +#define TRUE 1 + +#define HRESULT int +#define S_OK 0 +#define E_INVALIDARG -1 +#define E_OUTOFMEMORY -2 +#define E_FAIL -3 +#define E_INTERNAL_ERROR -4 +#define E_INVALIDDATA -5 + +#define MyMin( a, b ) ( a < b ? a : b ) + +#define MyMax( a, b ) ( a > b ? a : b ) + +#define kNumMoveBits 5 + +#define RETURN_IF_NOT_S_OK(x) { HRESULT __aResult_ = (x); if(__aResult_ != S_OK) return __aResult_; } + +#endif diff --git a/hostTools/lzma/decompress/RCDefs.h b/hostTools/lzma/decompress/RCDefs.h new file mode 100644 index 0000000..f260ab4 --- /dev/null +++ b/hostTools/lzma/decompress/RCDefs.h @@ -0,0 +1,43 @@ +#ifndef __RCDEFS_H +#define __RCDEFS_H + +#include "AriBitCoder.h" + +/* +#define RC_INIT_VAR \ + UINT32 aRange = aRangeDecoder->m_Range; \ + UINT32 aCode = aRangeDecoder->m_Code; + +#define RC_FLUSH_VAR \ + aRangeDecoder->m_Range = aRange; \ + aRangeDecoder->m_Code = aCode; +*/ + + +#if 1 +#define RC_GETBIT2(aNumMoveBits, aProb, aModelIndex, Action0, Action1) \ + {UINT32 aNewBound = (aRange >> kNumBitModelTotalBits) * aProb; \ + if (aCode < aNewBound) \ + { \ + Action0; \ + aRange = aNewBound; \ + aProb += (kBitModelTotal - aProb) >> aNumMoveBits; \ + aModelIndex <<= 1; \ + } \ + else \ + { \ + Action1; \ + aRange -= aNewBound; \ + aCode -= aNewBound; \ + aProb -= (aProb) >> aNumMoveBits; \ + aModelIndex = (aModelIndex << 1) + 1; \ + }} \ + if (aRange < kTopValue) \ + { \ + aCode = (aCode << 8) | InStreamReadByte(in_stream); \ + aRange <<= 8; } + +#define RC_GETBIT(aNumMoveBits, aProb, aModelIndex) RC_GETBIT2(aNumMoveBits, aProb, aModelIndex, ; , ;) +#endif + +#endif diff --git a/hostTools/lzma/decompress/RangeCoder.h b/hostTools/lzma/decompress/RangeCoder.h new file mode 100644 index 0000000..ae6f974 --- /dev/null +++ b/hostTools/lzma/decompress/RangeCoder.h @@ -0,0 +1,56 @@ +#ifndef __COMPRESSION_RANGECODER_H +#define __COMPRESSION_RANGECODER_H + +#include "IInOutStreams.h" + +#define kNumTopBits 24 +#define kTopValue (1 << kNumTopBits) + +typedef struct CRangeDecoder +{ + UINT32 m_Range; + UINT32 m_Code; +} CRangeDecoder; + + + +INLINE void RangeDecoderInit( + ISequentialInStream *in_stream, + CRangeDecoder *rangeDecoder) + { + int i; + rangeDecoder->m_Code = 0; + rangeDecoder->m_Range = (UINT32)(-1); + for(i = 0; i < 5; i++) + rangeDecoder->m_Code = (rangeDecoder->m_Code << 8) | InStreamReadByte(in_stream); + } + +INLINE UINT32 RangeDecodeDirectBits( + ISequentialInStream *in_stream, + CRangeDecoder *rangeDecoder, + UINT32 aNumTotalBits) + { + UINT32 aRange = rangeDecoder->m_Range; + UINT32 aCode = rangeDecoder->m_Code; + UINT32 aResult = 0; + UINT32 i; + for (i = aNumTotalBits; i > 0; i--) + { + UINT32 t; + aRange >>= 1; + t = (aCode - aRange) >> 31; + aCode -= aRange & (t - 1); + aResult = (aResult << 1) | (1 - t); + + if (aRange < kTopValue) + { + aCode = (aCode << 8) | InStreamReadByte(in_stream); + aRange <<= 8; + } + } + rangeDecoder->m_Range = aRange; + rangeDecoder->m_Code = aCode; + return aResult; + } + +#endif diff --git a/hostTools/lzma/decompress/WindowOut.h b/hostTools/lzma/decompress/WindowOut.h new file mode 100644 index 0000000..d774cac --- /dev/null +++ b/hostTools/lzma/decompress/WindowOut.h @@ -0,0 +1,47 @@ +#ifndef __STREAM_WINDOWOUT_H +#define __STREAM_WINDOWOUT_H + +#include "IInOutStreams.h" + +typedef struct WindowOut +{ + BYTE *Buffer; + UINT32 Pos; +} WindowOut; + +extern WindowOut out_window; + +#define OutWindowInit() \ + { \ + out_window.Buffer = (BYTE *) out_stream.data; \ + out_window.Pos = 0; \ + } + +#define OutWindowFlush() \ + { \ + OutStreamSizeSet( out_window.Pos ); \ + } + +// BRCM modification +INLINE void OutWindowCopyBackBlock(UINT32 aDistance, UINT32 aLen) + { + BYTE *p = out_window.Buffer + out_window.Pos; + UINT32 i; + aDistance++; + for(i = 0; i < aLen; i++) + p[i] = p[i - aDistance]; + out_window.Pos += aLen; + } + + +#define OutWindowPutOneByte(aByte) \ + { \ + out_window.Buffer[out_window.Pos++] = aByte; \ + } + +#define OutWindowGetOneByte(anIndex) \ + (out_window.Buffer[out_window.Pos + anIndex]) + + + +#endif diff --git a/hostTools/lzma/decompress/vxTypesOld.h b/hostTools/lzma/decompress/vxTypesOld.h new file mode 100644 index 0000000..7ee57bf --- /dev/null +++ b/hostTools/lzma/decompress/vxTypesOld.h @@ -0,0 +1,289 @@ +/* vxTypesOld.h - old VxWorks type definition header */ + +/* Copyright 1984-1997 Wind River Systems, Inc. */ + +/* +modification history +-------------------- +02c,15aug97,cym added simnt support. +02d,26mar97,cdp added Thumb (ARM7TDMI_T) support. +02c,28nov96,cdp added ARM support. +02b,28sep95,ms removed "static __inline__" (SPR #4500) +02b,12jul95,ism added simsolaris support +02a,19mar95,dvs removed tron references. +01z,01sep94,ism fixed comment as per SPR# 1512. +01y,02dec93,pme added Am29K family support. +01x,12jun93,rrr vxsim. +02a,26may94,yao added PPC support. +01w,09jun93,hdn added support for I80X86 +01v,12feb93,srh added C++ versions of FUNCPTR, et al. +01u,13nov92,dnw added definition of VOID (SPR #1781) +01t,02oct92,srh replaced conditional around volatile, const, and signed so + they won't be elided when __STDC__ is defined. + added __cplusplus to __STDC__ condition. +01s,22sep92,rrr added support for c++ +01r,08sep92,smb made some additions for the MIPS. +01q,07sep92,smb added __STDC__ and modes to maintain compatibility with 5.0 +01p,07jul92,rrr moved STACK_GROW and ENDIAN to vxArch.h +01o,03jul92,smb changed name from vxTypes.h. +01n,26may92,rrr the tree shuffle +01m,25nov91,llk included sys/types.h. +01l,04oct91,rrr passed through the ansification filter + -fixed #else and #endif + -removed TINY and UTINY + -changed VOID to void + -changed ASMLANGUAGE to _ASMLANGUAGE + -changed copyright notice +01k,01oct91,jpb fixed MIPS conditional for undefined CPU_FAMILY. +01j,20sep91,wmd conditionalized out defines for const, unsigned and volatile + for the MIPS architecture. +01i,02aug91,ajm added support for MIPS_R3k. +01h,15may91,gae added define for "signed" when not available for pre-ANSI. +01g,29apr91,hdn added defines and macros for TRON architecture. +01f,28apr91,del added defines of __volatile__ and __const__ if !_STDC_ + && _GNUC__ +01f,24mar91,del added INSTR * define for I960. +01e,28jan91,kdl added DBLFUNCPTR and FLTFUNCPTR. +01d,25oct90,dnw changed void to void except when linting. +01c,05oct90,shl added copyright notice. + made #endif ANSI style. +01b,10aug90,dnw added VOIDFUNCPTR +01a,29may90,del written. +*/ + +/* +DESCRIPTION +This header file contains a mixture of stuff. +1) the old style typedefs (ie. POSIX now says they must end with _t). + These will be phased out gradually. +2) a mechanism for getting rid of const warning which are produced by the + GNU C compiler. Hopefully, this will be removed in the future. +3) macros that are so longer needed for vxWorks source code but maybe needed + by some customer applications and are therefore provided for backward + compatability. +4) system III typedefs (used by netinet) which do not fit in anywhere else. + +*/ + +#ifndef __INCvxTypesOldh +#define __INCvxTypesOldh + +#ifdef __cplusplus +extern "C" { +#endif + +#include "sys/types.h" + +/* vxWorks types */ + +typedef char INT8; +typedef short INT16; +typedef int INT32; + +typedef unsigned char UINT8; +typedef unsigned short UINT16; +typedef unsigned int UINT32; + +typedef unsigned char UCHAR; +typedef unsigned short USHORT; +typedef unsigned int UINT; +typedef unsigned long ULONG; + +typedef int BOOL; +typedef int STATUS; +typedef int ARGINT; + +typedef void VOID; + +#ifdef __cplusplus +typedef int (*FUNCPTR) (...); /* ptr to function returning int */ +typedef void (*VOIDFUNCPTR) (...); /* ptr to function returning void */ +typedef double (*DBLFUNCPTR) (...); /* ptr to function returning double*/ +typedef float (*FLTFUNCPTR) (...); /* ptr to function returning float */ +#else +typedef int (*FUNCPTR) (); /* ptr to function returning int */ +typedef void (*VOIDFUNCPTR) (); /* ptr to function returning void */ +typedef double (*DBLFUNCPTR) (); /* ptr to function returning double*/ +typedef float (*FLTFUNCPTR) (); /* ptr to function returning float */ +#endif /* _cplusplus */ + + +/* This structure and the following definitions are needed to get rid + of const warning produced by the GNU C compiler. + */ + +#if defined(__STDC__) || defined(__cplusplus) +typedef union + { + long pm_int; + void *pm_v; + const void *pm_cv; + char *pm_c; + unsigned char *pm_uc; + + signed char *pm_sc; + const char *pm_cc; + const unsigned char *pm_cuc; + const signed char *pm_csc; + short *pm_s; + ushort_t *pm_us; + const short *pm_cs; + const ushort_t *pm_cus; + int *pm_i; + uint_t *pm_ui; + const int *pm_ci; + const uint_t *pm_cui; + long *pm_l; + ulong_t *pm_ul; + const long *pm_cl; + const ulong_t *pm_cul; + + int8_t *pm_i8; + uint8_t *pm_ui8; + const int8_t *pm_ci8; + const uint8_t *pm_cui8; + int16_t *pm_i16; + uint16_t *pm_ui16; + const int16_t *pm_ci16; + const uint16_t *pm_cui16; + int32_t *pm_i32; + uint32_t *pm_ui32; + const int32_t *pm_ci32; + const uint32_t *pm_cui32; +#if _ARCH_MOVE_SIZE > 4 + int64_t *pm_i64; + const int64_t *pm_ci64; +#if _ARCH_MOVE_SIZE > 8 + int128_t *pm_i128; + const int128_t *pm_ci128; +#endif +#endif + } pointer_mix_t; + +#define CHAR_FROM_CONST(x) (char *)(x) +#define VOID_FROM_CONST(x) (void *)(x) + +#endif /* __STDC__ */ + +#define STACK_DIR _ARCH_STACK_DIR +#define ALIGN_MEMORY _ARCH_ALIGN_MEMORY +#define ALIGN_STACK _ARCH_ALIGN_STACK +#define ALIGN_REGS _ARCH_ALIGN_REGS + +#define NBBY 8 /* number of bits in a byte */ + +/* modes - must match O_RDONLY/O_WRONLY/O_RDWR in ioLib.h! */ + +#define READ 0 +#define WRITE 1 +#define UPDATE 2 + +/* Select uses bit masks of file descriptors in longs. + * These macros manipulate such bit fields (the filesystem macros use chars). + * FD_SETSIZE may be defined by the user, but the default here + * should be >= maxFiles parameter in iosInit call found in usrConfig.c. + * If this define is changed, recompile the source, or else select() will + * not work. + */ + +#ifndef FD_SETSIZE +#define FD_SETSIZE 256 +#endif /* FD_SETSIZE */ + +typedef long fd_mask; +#define NFDBITS (sizeof(fd_mask) * NBBY) /* bits per mask */ +#ifndef howmany +#define howmany(x, y) ((unsigned int)(((x)+((y)-1)))/(unsigned int)(y)) +#endif /* howmany */ + +typedef struct fd_set + { + fd_mask fds_bits[howmany(FD_SETSIZE, NFDBITS)]; + } fd_set; + +#define FD_SET(n, p) ((p)->fds_bits[(n)/NFDBITS] |= (1 << ((n) % NFDBITS))) +#define FD_CLR(n, p) ((p)->fds_bits[(n)/NFDBITS] &= ~(1 << ((n) % NFDBITS))) +#define FD_ISSET(n, p) ((p)->fds_bits[(n)/NFDBITS] & (1 << ((n) % NFDBITS))) +#define FD_ZERO(p) bzero((char *)(p), sizeof(*(p))) + + +/* system III typedefs (used by netinet) */ + +typedef unsigned char u_char; +typedef unsigned short u_short; +typedef unsigned int u_int; +typedef unsigned long u_long; +typedef unsigned short ushort; + + +/* historical definitions - now obsolete */ + +typedef char TBOOL; /* obsolete */ + + +/* architecture dependent typedefs */ + +#ifdef CPU_FAMILY + +#if CPU_FAMILY==MC680X0 +typedef unsigned short INSTR; /* word-aligned instructions */ +#endif /* CPU_FAMILY==MC680X0 */ + +#if CPU_FAMILY==SPARC || CPU_FAMILY==MIPS || CPU_FAMILY==SIMSPARCSUNOS || CPU_FAMILY==SIMHPPA || CPU_FAMILY==SIMSPARCSOLARIS +typedef unsigned long INSTR; /* 32 bit word-aligned instructions */ +#endif /* CPU_FAMILY==SPARC || CPU_FAMILY==MIPS || CPU_FAMILY==SIMSPARCSUNOS || CPU_FAMILY==SIMHPPA || CPU_FAMILY==SIMSPARCSOLARIS */ + +#if CPU_FAMILY==I960 +typedef unsigned long INSTR; /* 32 bit word-aligned instructions */ +#endif /* CPU_FAMILY==I960 */ + +#if CPU_FAMILY==I80X86 || CPU_FAMILY==SIMNT +typedef unsigned char INSTR; /* char instructions */ +#endif /* CPU_FAMILY==I80X86 || CPU_FAMILY==SIMNT */ + +#if CPU_FAMILY==AM29XXX +typedef unsigned long INSTR; /* 32 bit word-aligned instructions */ +#endif /* CPU_FAMILY==AM29XXX */ + +#if (CPU_FAMILY==PPC) +typedef unsigned long INSTR; /* 32 bit word-aligned instructions */ +#endif /* (CPU_FAMILY==PPC) */ + +#if CPU_FAMILY==ARM +#if CPU==ARM7TDMI_T +typedef unsigned short INSTR; /* 16 bit instructions */ +#else +typedef unsigned long INSTR; /* 32 bit word-aligned instructions */ +#endif +#endif /* CPU_FAMILY==ARM */ + +#endif /* CPU_FAMILY */ + +/* ANSI type qualifiers */ + +#if !defined(__STDC__) && !defined(__cplusplus) + +#ifdef __GNUC__ +#define volatile __volatile__ +#define const __const__ +#define signed __signed__ +#else +#if !(defined(CPU_FAMILY) && CPU_FAMILY==MIPS) +#define volatile +#define const +#define signed +#endif /* !(defined(CPU_FAMILY) && CPU_FAMILY==MIPS) */ +#endif /* __GNUC__ */ + +#endif /* !defined(__STDC__) && !defined(__cplusplus) */ + +#if CPU_FAMILY==MIPS +#define CHAR_FROM_CONST(x) (char *)(x) +#define VOID_FROM_CONST(x) (void *)(x) +#endif + +#ifdef __cplusplus +} +#endif + +#endif /* __INCvxTypesOldh */ -- cgit v1.2.3