From b7b56dd8fbe123958e196f396dab5ff3000b68dd Mon Sep 17 00:00:00 2001 From: Patrick Georgi Date: Mon, 14 Sep 2009 13:29:27 +0000 Subject: New cbfstool. Works without mmap or fork/exec and supports fixed location files. Some parts are salvaged from the pre-commit version (esp. stage and payload creation), others are completely rewritten (eg. the main loop that handles file addition) Also adapt newconfig (we don't need cbfs/tools anymore) and fix some minor issues in the cbfstool-README. Signed-off-by: Patrick Georgi Acked-by: Stefan Reinauer git-svn-id: svn://svn.coreboot.org/coreboot/trunk@4630 2b7e53f0-3cfb-0310-b3e9-8179ed1497e1 --- util/cbfstool/lzma/C/7zip/Common/InBuffer.h | 76 + util/cbfstool/lzma/C/7zip/Common/OutBuffer.cpp | 116 ++ util/cbfstool/lzma/C/7zip/Common/OutBuffer.h | 64 + util/cbfstool/lzma/C/7zip/Common/StdAfx.h | 9 + util/cbfstool/lzma/C/7zip/Common/StreamUtils.cpp | 44 + util/cbfstool/lzma/C/7zip/Common/StreamUtils.h | 11 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTree.h | 54 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h | 12 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h | 16 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h | 18 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h | 531 +++++++ .../lzma/C/7zip/Compress/LZ/HashChain/HC4.h | 19 + .../lzma/C/7zip/Compress/LZ/HashChain/HCMain.h | 6 + .../lzma/C/7zip/Compress/LZ/IMatchFinder.h | 33 + .../lzma/C/7zip/Compress/LZ/LZInWindow.cpp | 105 ++ util/cbfstool/lzma/C/7zip/Compress/LZ/LZInWindow.h | 87 ++ util/cbfstool/lzma/C/7zip/Compress/LZ/StdAfx.h | 6 + util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMA.h | 82 + .../lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp | 1564 ++++++++++++++++++++ .../lzma/C/7zip/Compress/LZMA/LZMAEncoder.h | 411 +++++ util/cbfstool/lzma/C/7zip/Compress/LZMA/StdAfx.h | 8 + .../lzma/C/7zip/Compress/RangeCoder/RangeCoder.h | 205 +++ .../C/7zip/Compress/RangeCoder/RangeCoderBit.cpp | 80 + .../C/7zip/Compress/RangeCoder/RangeCoderBit.h | 120 ++ .../C/7zip/Compress/RangeCoder/RangeCoderBitTree.h | 161 ++ .../C/7zip/Compress/RangeCoder/RangeCoderOpt.h | 31 + .../lzma/C/7zip/Compress/RangeCoder/StdAfx.h | 6 + util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.c | 588 ++++++++ util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.h | 131 ++ util/cbfstool/lzma/C/7zip/ICoder.h | 163 ++ util/cbfstool/lzma/C/7zip/IStream.h | 62 + util/cbfstool/lzma/C/Common/Alloc.cpp | 118 ++ util/cbfstool/lzma/C/Common/Alloc.h | 29 + util/cbfstool/lzma/C/Common/CRC.cpp | 61 + util/cbfstool/lzma/C/Common/CRC.h | 36 + util/cbfstool/lzma/C/Common/Defs.h | 20 + util/cbfstool/lzma/C/Common/MyCom.h | 203 +++ util/cbfstool/lzma/C/Common/MyGuidDef.h | 54 + util/cbfstool/lzma/C/Common/MyInitGuid.h | 13 + util/cbfstool/lzma/C/Common/MyUnknown.h | 24 + util/cbfstool/lzma/C/Common/MyWindows.h | 201 +++ util/cbfstool/lzma/C/Common/NewHandler.h | 16 + util/cbfstool/lzma/C/Common/StdAfx.h | 9 + util/cbfstool/lzma/C/Common/Types.h | 19 + util/cbfstool/lzma/C/LGPL.txt | 504 +++++++ util/cbfstool/lzma/C/ORIGIN | 3 + util/cbfstool/lzma/Makefile | 50 + util/cbfstool/lzma/Makefile.inc | 60 + util/cbfstool/lzma/minilzma.cc | 318 ++++ 49 files changed, 6557 insertions(+) create mode 100644 util/cbfstool/lzma/C/7zip/Common/InBuffer.h create mode 100644 util/cbfstool/lzma/C/7zip/Common/OutBuffer.cpp create mode 100644 util/cbfstool/lzma/C/7zip/Common/OutBuffer.h create mode 100644 util/cbfstool/lzma/C/7zip/Common/StdAfx.h create mode 100644 util/cbfstool/lzma/C/7zip/Common/StreamUtils.cpp create mode 100644 util/cbfstool/lzma/C/7zip/Common/StreamUtils.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/HashChain/HC4.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/IMatchFinder.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/LZInWindow.cpp create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/LZInWindow.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZ/StdAfx.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMA.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMAEncoder.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/LZMA/StdAfx.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoder.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.cpp create mode 100644 util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBitTree.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderOpt.h create mode 100644 util/cbfstool/lzma/C/7zip/Compress/RangeCoder/StdAfx.h create mode 100644 util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.c create mode 100644 util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.h create mode 100644 util/cbfstool/lzma/C/7zip/ICoder.h create mode 100644 util/cbfstool/lzma/C/7zip/IStream.h create mode 100644 util/cbfstool/lzma/C/Common/Alloc.cpp create mode 100644 util/cbfstool/lzma/C/Common/Alloc.h create mode 100644 util/cbfstool/lzma/C/Common/CRC.cpp create mode 100644 util/cbfstool/lzma/C/Common/CRC.h create mode 100644 util/cbfstool/lzma/C/Common/Defs.h create mode 100644 util/cbfstool/lzma/C/Common/MyCom.h create mode 100644 util/cbfstool/lzma/C/Common/MyGuidDef.h create mode 100644 util/cbfstool/lzma/C/Common/MyInitGuid.h create mode 100644 util/cbfstool/lzma/C/Common/MyUnknown.h create mode 100644 util/cbfstool/lzma/C/Common/MyWindows.h create mode 100644 util/cbfstool/lzma/C/Common/NewHandler.h create mode 100644 util/cbfstool/lzma/C/Common/StdAfx.h create mode 100644 util/cbfstool/lzma/C/Common/Types.h create mode 100644 util/cbfstool/lzma/C/LGPL.txt create mode 100644 util/cbfstool/lzma/C/ORIGIN create mode 100644 util/cbfstool/lzma/Makefile create mode 100644 util/cbfstool/lzma/Makefile.inc create mode 100644 util/cbfstool/lzma/minilzma.cc (limited to 'util/cbfstool/lzma') diff --git a/util/cbfstool/lzma/C/7zip/Common/InBuffer.h b/util/cbfstool/lzma/C/7zip/Common/InBuffer.h new file mode 100644 index 0000000000..057caa1659 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Common/InBuffer.h @@ -0,0 +1,76 @@ +// InBuffer.h + +#ifndef __INBUFFER_H +#define __INBUFFER_H + +#include "../IStream.h" +#include "../../Common/MyCom.h" + +#ifndef _NO_EXCEPTIONS +class CInBufferException +{ +public: + HRESULT ErrorCode; + CInBufferException(HRESULT errorCode): ErrorCode(errorCode) {} +}; +#endif + +class CInBuffer +{ + Byte *_buffer; + Byte *_bufferLimit; + Byte *_bufferBase; + CMyComPtr _stream; + UInt64 _processedSize; + UInt32 _bufferSize; + bool _wasFinished; + + bool ReadBlock(); + Byte ReadBlock2(); + +public: + #ifdef _NO_EXCEPTIONS + HRESULT ErrorCode; + #endif + + CInBuffer(); + ~CInBuffer() { Free(); } + + bool Create(UInt32 bufferSize); + void Free(); + + void SetStream(ISequentialInStream *stream); + void Init(); + void ReleaseStream() { _stream.Release(); } + + bool ReadByte(Byte &b) + { + if(_buffer >= _bufferLimit) + if(!ReadBlock()) + return false; + b = *_buffer++; + return true; + } + Byte ReadByte() + { + if(_buffer >= _bufferLimit) + return ReadBlock2(); + return *_buffer++; + } + void ReadBytes(void *data, UInt32 size, UInt32 &processedSize) + { + for(processedSize = 0; processedSize < size; processedSize++) + if (!ReadByte(((Byte *)data)[processedSize])) + return; + } + bool ReadBytes(void *data, UInt32 size) + { + UInt32 processedSize; + ReadBytes(data, size, processedSize); + return (processedSize == size); + } + UInt64 GetProcessedSize() const { return _processedSize + (_buffer - _bufferBase); } + bool WasFinished() const { return _wasFinished; } +}; + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Common/OutBuffer.cpp b/util/cbfstool/lzma/C/7zip/Common/OutBuffer.cpp new file mode 100644 index 0000000000..a73fa7c5b9 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Common/OutBuffer.cpp @@ -0,0 +1,116 @@ +// OutByte.cpp + +#include "StdAfx.h" + +#include "OutBuffer.h" + +#include "../../Common/Alloc.h" + +bool COutBuffer::Create(UInt32 bufferSize) +{ + const UInt32 kMinBlockSize = 1; + if (bufferSize < kMinBlockSize) + bufferSize = kMinBlockSize; + if (_buffer != 0 && _bufferSize == bufferSize) + return true; + Free(); + _bufferSize = bufferSize; + _buffer = (Byte *)::MidAlloc(bufferSize); + return (_buffer != 0); +} + +void COutBuffer::Free() +{ + ::MidFree(_buffer); + _buffer = 0; +} + +void COutBuffer::SetStream(ISequentialOutStream *stream) +{ + _stream = stream; +} + +void COutBuffer::Init() +{ + _streamPos = 0; + _limitPos = _bufferSize; + _pos = 0; + _processedSize = 0; + _overDict = false; + #ifdef _NO_EXCEPTIONS + ErrorCode = S_OK; + #endif +} + +UInt64 COutBuffer::GetProcessedSize() const +{ + UInt64 res = _processedSize + _pos - _streamPos; + if (_streamPos > _pos) + res += _bufferSize; + return res; +} + + +HRESULT COutBuffer::FlushPart() +{ + // _streamPos < _bufferSize + UInt32 size = (_streamPos >= _pos) ? (_bufferSize - _streamPos) : (_pos - _streamPos); + HRESULT result = S_OK; + #ifdef _NO_EXCEPTIONS + result = ErrorCode; + #endif + if (_buffer2 != 0) + { + memmove(_buffer2, _buffer + _streamPos, size); + _buffer2 += size; + } + + if (_stream != 0 + #ifdef _NO_EXCEPTIONS + && (ErrorCode == S_OK) + #endif + ) + { + UInt32 processedSize = 0; + result = _stream->Write(_buffer + _streamPos, size, &processedSize); + size = processedSize; + } + _streamPos += size; + if (_streamPos == _bufferSize) + _streamPos = 0; + if (_pos == _bufferSize) + { + _overDict = true; + _pos = 0; + } + _limitPos = (_streamPos > _pos) ? _streamPos : _bufferSize; + _processedSize += size; + return result; +} + +HRESULT COutBuffer::Flush() +{ + #ifdef _NO_EXCEPTIONS + if (ErrorCode != S_OK) + return ErrorCode; + #endif + + while(_streamPos != _pos) + { + HRESULT result = FlushPart(); + if (result != S_OK) + return result; + } + return S_OK; +} + +void COutBuffer::FlushWithCheck() +{ + HRESULT result = FlushPart(); + #ifdef _NO_EXCEPTIONS + ErrorCode = result; + #else + if (result != S_OK) + throw COutBufferException(result); + #endif +} diff --git a/util/cbfstool/lzma/C/7zip/Common/OutBuffer.h b/util/cbfstool/lzma/C/7zip/Common/OutBuffer.h new file mode 100644 index 0000000000..0ce54e21e6 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Common/OutBuffer.h @@ -0,0 +1,64 @@ +// OutBuffer.h + +#ifndef __OUTBUFFER_H +#define __OUTBUFFER_H + +#include "../IStream.h" +#include "../../Common/MyCom.h" + +#ifndef _NO_EXCEPTIONS +struct COutBufferException +{ + HRESULT ErrorCode; + COutBufferException(HRESULT errorCode): ErrorCode(errorCode) {} +}; +#endif + +class COutBuffer +{ +protected: + Byte *_buffer; + UInt32 _pos; + UInt32 _limitPos; + UInt32 _streamPos; + UInt32 _bufferSize; + CMyComPtr _stream; + UInt64 _processedSize; + Byte *_buffer2; + bool _overDict; + + HRESULT FlushPart(); + void FlushWithCheck(); +public: + #ifdef _NO_EXCEPTIONS + HRESULT ErrorCode; + #endif + + COutBuffer(): _buffer(0), _pos(0), _stream(0), _buffer2(0) {} + ~COutBuffer() { Free(); } + + bool Create(UInt32 bufferSize); + void Free(); + + void SetMemStream(Byte *buffer) { _buffer2 = buffer; } + void SetStream(ISequentialOutStream *stream); + void Init(); + HRESULT Flush(); + void ReleaseStream() { _stream.Release(); } + + void WriteByte(Byte b) + { + _buffer[_pos++] = b; + if(_pos == _limitPos) + FlushWithCheck(); + } + void WriteBytes(const void *data, size_t size) + { + for (size_t i = 0; i < size; i++) + WriteByte(((const Byte *)data)[i]); + } + + UInt64 GetProcessedSize() const; +}; + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Common/StdAfx.h b/util/cbfstool/lzma/C/7zip/Common/StdAfx.h new file mode 100644 index 0000000000..27a77b104b --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Common/StdAfx.h @@ -0,0 +1,9 @@ +// StdAfx.h + +#ifndef __STDAFX_H +#define __STDAFX_H + +#include "../../Common/MyWindows.h" +#include "../../Common/NewHandler.h" + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Common/StreamUtils.cpp b/util/cbfstool/lzma/C/7zip/Common/StreamUtils.cpp new file mode 100644 index 0000000000..a5d9ac0ef0 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Common/StreamUtils.cpp @@ -0,0 +1,44 @@ +// StreamUtils.cpp + +#include "StdAfx.h" + +#include "../../Common/MyCom.h" +#include "StreamUtils.h" + +HRESULT ReadStream(ISequentialInStream *stream, void *data, UInt32 size, UInt32 *processedSize) +{ + if (processedSize != 0) + *processedSize = 0; + while(size != 0) + { + UInt32 processedSizeLoc; + HRESULT res = stream->Read(data, size, &processedSizeLoc); + if (processedSize != 0) + *processedSize += processedSizeLoc; + data = (Byte *)((Byte *)data + processedSizeLoc); + size -= processedSizeLoc; + RINOK(res); + if (processedSizeLoc == 0) + return S_OK; + } + return S_OK; +} + +HRESULT WriteStream(ISequentialOutStream *stream, const void *data, UInt32 size, UInt32 *processedSize) +{ + if (processedSize != 0) + *processedSize = 0; + while(size != 0) + { + UInt32 processedSizeLoc; + HRESULT res = stream->Write(data, size, &processedSizeLoc); + if (processedSize != 0) + *processedSize += processedSizeLoc; + data = (const void *)((const Byte *)data + processedSizeLoc); + size -= processedSizeLoc; + RINOK(res); + if (processedSizeLoc == 0) + break; + } + return S_OK; +} diff --git a/util/cbfstool/lzma/C/7zip/Common/StreamUtils.h b/util/cbfstool/lzma/C/7zip/Common/StreamUtils.h new file mode 100644 index 0000000000..59f88733f6 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Common/StreamUtils.h @@ -0,0 +1,11 @@ +// StreamUtils.h + +#ifndef __STREAMUTILS_H +#define __STREAMUTILS_H + +#include "../IStream.h" + +HRESULT ReadStream(ISequentialInStream *stream, void *data, UInt32 size, UInt32 *processedSize); +HRESULT WriteStream(ISequentialOutStream *stream, const void *data, UInt32 size, UInt32 *processedSize); + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h new file mode 100644 index 0000000000..b3b3f13a56 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h @@ -0,0 +1,54 @@ +// BinTree.h + +#include "../LZInWindow.h" +#include "../IMatchFinder.h" + +namespace BT_NAMESPACE { + +typedef UInt32 CIndex; +const UInt32 kMaxValForNormalize = (UInt32(1) << 31) - 1; + +class CMatchFinder: + public IMatchFinder, + public CLZInWindow, + public CMyUnknownImp, + public IMatchFinderSetNumPasses +{ + UInt32 _cyclicBufferPos; + UInt32 _cyclicBufferSize; // it must be historySize + 1 + UInt32 _matchMaxLen; + CIndex *_hash; + CIndex *_son; + UInt32 _hashMask; + UInt32 _cutValue; + UInt32 _hashSizeSum; + + void Normalize(); + void FreeThisClassMemory(); + void FreeMemory(); + + MY_UNKNOWN_IMP + + STDMETHOD(SetStream)(ISequentialInStream *inStream); + STDMETHOD_(void, ReleaseStream)(); + STDMETHOD(Init)(); + HRESULT MovePos(); + STDMETHOD_(Byte, GetIndexByte)(Int32 index); + STDMETHOD_(UInt32, GetMatchLen)(Int32 index, UInt32 back, UInt32 limit); + STDMETHOD_(UInt32, GetNumAvailableBytes)(); + STDMETHOD_(const Byte *, GetPointerToCurrentPos)(); + STDMETHOD_(Int32, NeedChangeBufferPos)(UInt32 numCheckBytes); + STDMETHOD_(void, ChangeBufferPos)(); + + STDMETHOD(Create)(UInt32 historySize, UInt32 keepAddBufferBefore, + UInt32 matchMaxLen, UInt32 keepAddBufferAfter); + STDMETHOD(GetMatches)(UInt32 *distances); + STDMETHOD(Skip)(UInt32 num); + +public: + CMatchFinder(); + virtual ~CMatchFinder(); + virtual void SetNumPasses(UInt32 numPasses) { _cutValue = numPasses; } +}; + +} diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h new file mode 100644 index 0000000000..74ca8d9d0e --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h @@ -0,0 +1,12 @@ +// BinTree2.h + +#ifndef __BINTREE2_H +#define __BINTREE2_H + +#define BT_NAMESPACE NBT2 + +#include "BinTreeMain.h" + +#undef BT_NAMESPACE + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h new file mode 100644 index 0000000000..76bd9ddd43 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h @@ -0,0 +1,16 @@ +// BinTree3.h + +#ifndef __BINTREE3_H +#define __BINTREE3_H + +#define BT_NAMESPACE NBT3 + +#define HASH_ARRAY_2 + +#include "BinTreeMain.h" + +#undef HASH_ARRAY_2 + +#undef BT_NAMESPACE + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h new file mode 100644 index 0000000000..08e2d1ced6 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h @@ -0,0 +1,18 @@ +// BinTree4.h + +#ifndef __BINTREE4_H +#define __BINTREE4_H + +#define BT_NAMESPACE NBT4 + +#define HASH_ARRAY_2 +#define HASH_ARRAY_3 + +#include "BinTreeMain.h" + +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 + +#undef BT_NAMESPACE + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h new file mode 100644 index 0000000000..7a6f621a06 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h @@ -0,0 +1,531 @@ +// BinTreeMain.h + +#include "../../../../Common/Defs.h" +#include "../../../../Common/CRC.h" +#include "../../../../Common/Alloc.h" + +#include "BinTree.h" + +// #include +// It's for prefetch +// But prefetch doesn't give big gain in K8. + +namespace BT_NAMESPACE { + +#ifdef HASH_ARRAY_2 + static const UInt32 kHash2Size = 1 << 10; + #define kNumHashDirectBytes 0 + #ifdef HASH_ARRAY_3 + static const UInt32 kNumHashBytes = 4; + static const UInt32 kHash3Size = 1 << 16; + #else + static const UInt32 kNumHashBytes = 3; + #endif + static const UInt32 kHashSize = 0; + static const UInt32 kMinMatchCheck = kNumHashBytes; + static const UInt32 kStartMaxLen = 1; +#else + #ifdef HASH_ZIP + #define kNumHashDirectBytes 0 + static const UInt32 kNumHashBytes = 3; + static const UInt32 kHashSize = 1 << 16; + static const UInt32 kMinMatchCheck = kNumHashBytes; + static const UInt32 kStartMaxLen = 1; + #else + #define kNumHashDirectBytes 2 + static const UInt32 kNumHashBytes = 2; + static const UInt32 kHashSize = 1 << (8 * kNumHashBytes); + static const UInt32 kMinMatchCheck = kNumHashBytes + 1; + static const UInt32 kStartMaxLen = 1; + #endif +#endif + +#ifdef HASH_ARRAY_2 +#ifdef HASH_ARRAY_3 +static const UInt32 kHash3Offset = kHash2Size; +#endif +#endif + +static const UInt32 kFixHashSize = 0 + #ifdef HASH_ARRAY_2 + + kHash2Size + #ifdef HASH_ARRAY_3 + + kHash3Size + #endif + #endif + ; + +CMatchFinder::CMatchFinder(): + _hash(0) +{ +} + +void CMatchFinder::FreeThisClassMemory() +{ + BigFree(_hash); + _hash = 0; +} + +void CMatchFinder::FreeMemory() +{ + FreeThisClassMemory(); + CLZInWindow::Free(); +} + +CMatchFinder::~CMatchFinder() +{ + FreeMemory(); +} + +STDMETHODIMP CMatchFinder::Create(UInt32 historySize, UInt32 keepAddBufferBefore, + UInt32 matchMaxLen, UInt32 keepAddBufferAfter) +{ + if (historySize > kMaxValForNormalize - 256) + { + FreeMemory(); + return E_INVALIDARG; + } + _cutValue = + #ifdef _HASH_CHAIN + 8 + (matchMaxLen >> 2); + #else + 16 + (matchMaxLen >> 1); + #endif + UInt32 sizeReserv = (historySize + keepAddBufferBefore + + matchMaxLen + keepAddBufferAfter) / 2 + 256; + if (CLZInWindow::Create(historySize + keepAddBufferBefore, + matchMaxLen + keepAddBufferAfter, sizeReserv)) + { + _matchMaxLen = matchMaxLen; + UInt32 newCyclicBufferSize = historySize + 1; + if (_hash != 0 && newCyclicBufferSize == _cyclicBufferSize) + return S_OK; + FreeThisClassMemory(); + _cyclicBufferSize = newCyclicBufferSize; // don't change it + + UInt32 hs = kHashSize; + + #ifdef HASH_ARRAY_2 + hs = historySize - 1; + hs |= (hs >> 1); + hs |= (hs >> 2); + hs |= (hs >> 4); + hs |= (hs >> 8); + hs >>= 1; + hs |= 0xFFFF; + if (hs > (1 << 24)) + { + #ifdef HASH_ARRAY_3 + hs >>= 1; + #else + hs = (1 << 24) - 1; + #endif + } + _hashMask = hs; + hs++; + #endif + _hashSizeSum = hs + kFixHashSize; + UInt32 numItems = _hashSizeSum + _cyclicBufferSize + #ifndef _HASH_CHAIN + * 2 + #endif + ; + size_t sizeInBytes = (size_t)numItems * sizeof(CIndex); + if (sizeInBytes / sizeof(CIndex) != numItems) + return E_OUTOFMEMORY; + _hash = (CIndex *)BigAlloc(sizeInBytes); + _son = _hash + _hashSizeSum; + if (_hash != 0) + return S_OK; + } + FreeMemory(); + return E_OUTOFMEMORY; +} + +static const UInt32 kEmptyHashValue = 0; + +STDMETHODIMP CMatchFinder::SetStream(ISequentialInStream *stream) +{ + CLZInWindow::SetStream(stream); + return S_OK; +} + +STDMETHODIMP CMatchFinder::Init() +{ + RINOK(CLZInWindow::Init()); + for(UInt32 i = 0; i < _hashSizeSum; i++) + _hash[i] = kEmptyHashValue; + _cyclicBufferPos = 0; + ReduceOffsets(-1); + return S_OK; +} + +STDMETHODIMP_(void) CMatchFinder::ReleaseStream() +{ + // ReleaseStream(); +} + +#ifdef HASH_ARRAY_2 +#ifdef HASH_ARRAY_3 + +#define HASH_CALC { \ + UInt32 temp = CCRC::Table[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hash3Value = (temp ^ (UInt32(cur[2]) << 8)) & (kHash3Size - 1); \ + hashValue = (temp ^ (UInt32(cur[2]) << 8) ^ (CCRC::Table[cur[3]] << 5)) & _hashMask; } + +#else // no HASH_ARRAY_3 +#define HASH_CALC { \ + UInt32 temp = CCRC::Table[cur[0]] ^ cur[1]; \ + hash2Value = temp & (kHash2Size - 1); \ + hashValue = (temp ^ (UInt32(cur[2]) << 8)) & _hashMask; } +#endif // HASH_ARRAY_3 +#else // no HASH_ARRAY_2 +#ifdef HASH_ZIP +inline UInt32 Hash(const Byte *pointer) +{ + return ((UInt32(pointer[0]) << 8) ^ CCRC::Table[pointer[1]] ^ pointer[2]) & (kHashSize - 1); +} +#else // no HASH_ZIP +inline UInt32 Hash(const Byte *pointer) +{ + return pointer[0] ^ (UInt32(pointer[1]) << 8); +} +#endif // HASH_ZIP +#endif // HASH_ARRAY_2 + +STDMETHODIMP CMatchFinder::GetMatches(UInt32 *distances) +{ + UInt32 lenLimit; + if (_pos + _matchMaxLen <= _streamPos) + lenLimit = _matchMaxLen; + else + { + lenLimit = _streamPos - _pos; + if(lenLimit < kMinMatchCheck) + { + distances[0] = 0; + return MovePos(); + } + } + + int offset = 1; + + UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; + const Byte *cur = _buffer + _pos; + + UInt32 maxLen = kStartMaxLen; // to avoid items for len < hashSize; + + #ifdef HASH_ARRAY_2 + UInt32 hash2Value; + #ifdef HASH_ARRAY_3 + UInt32 hash3Value; + #endif + UInt32 hashValue; + HASH_CALC; + #else + UInt32 hashValue = Hash(cur); + #endif + + UInt32 curMatch = _hash[kFixHashSize + hashValue]; + #ifdef HASH_ARRAY_2 + UInt32 curMatch2 = _hash[hash2Value]; + #ifdef HASH_ARRAY_3 + UInt32 curMatch3 = _hash[kHash3Offset + hash3Value]; + #endif + _hash[hash2Value] = _pos; + if(curMatch2 > matchMinPos) + if (_buffer[curMatch2] == cur[0]) + { + distances[offset++] = maxLen = 2; + distances[offset++] = _pos - curMatch2 - 1; + } + + #ifdef HASH_ARRAY_3 + _hash[kHash3Offset + hash3Value] = _pos; + if(curMatch3 > matchMinPos) + if (_buffer[curMatch3] == cur[0]) + { + if (curMatch3 == curMatch2) + offset -= 2; + distances[offset++] = maxLen = 3; + distances[offset++] = _pos - curMatch3 - 1; + curMatch2 = curMatch3; + } + #endif + if (offset != 1 && curMatch2 == curMatch) + { + offset -= 2; + maxLen = kStartMaxLen; + } + #endif + + _hash[kFixHashSize + hashValue] = _pos; + + CIndex *son = _son; + + #ifdef _HASH_CHAIN + son[_cyclicBufferPos] = curMatch; + #else + CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1; + CIndex *ptr1 = son + (_cyclicBufferPos << 1); + + UInt32 len0, len1; + len0 = len1 = kNumHashDirectBytes; + #endif + + #if kNumHashDirectBytes != 0 + if(curMatch > matchMinPos) + { + if (_buffer[curMatch + kNumHashDirectBytes] != cur[kNumHashDirectBytes]) + { + distances[offset++] = maxLen = kNumHashDirectBytes; + distances[offset++] = _pos - curMatch - 1; + } + } + #endif + UInt32 count = _cutValue; + while(true) + { + if(curMatch <= matchMinPos || count-- == 0) + { + #ifndef _HASH_CHAIN + *ptr0 = *ptr1 = kEmptyHashValue; + #endif + break; + } + UInt32 delta = _pos - curMatch; + UInt32 cyclicPos = (delta <= _cyclicBufferPos) ? + (_cyclicBufferPos - delta): + (_cyclicBufferPos - delta + _cyclicBufferSize); + CIndex *pair = son + + #ifdef _HASH_CHAIN + cyclicPos; + #else + (cyclicPos << 1); + #endif + + // _mm_prefetch((const char *)pair, _MM_HINT_T0); + + const Byte *pb = _buffer + curMatch; + UInt32 len = + #ifdef _HASH_CHAIN + kNumHashDirectBytes; + if (pb[maxLen] == cur[maxLen]) + #else + MyMin(len0, len1); + #endif + if (pb[len] == cur[len]) + { + while(++len != lenLimit) + if (pb[len] != cur[len]) + break; + if (maxLen < len) + { + distances[offset++] = maxLen = len; + distances[offset++] = delta - 1; + if (len == lenLimit) + { + #ifndef _HASH_CHAIN + *ptr1 = pair[0]; + *ptr0 = pair[1]; + #endif + break; + } + } + } + #ifdef _HASH_CHAIN + curMatch = *pair; + #else + if (pb[len] < cur[len]) + { + *ptr1 = curMatch; + ptr1 = pair + 1; + curMatch = *ptr1; + len1 = len; + } + else + { + *ptr0 = curMatch; + ptr0 = pair; + curMatch = *ptr0; + len0 = len; + } + #endif + } + distances[0] = offset - 1; + if (++_cyclicBufferPos == _cyclicBufferSize) + _cyclicBufferPos = 0; + RINOK(CLZInWindow::MovePos()); + if (_pos == kMaxValForNormalize) + Normalize(); + return S_OK; +} + +STDMETHODIMP CMatchFinder::Skip(UInt32 num) +{ + do + { + #ifdef _HASH_CHAIN + if (_streamPos - _pos < kNumHashBytes) + { + RINOK(MovePos()); + continue; + } + #else + UInt32 lenLimit; + if (_pos + _matchMaxLen <= _streamPos) + lenLimit = _matchMaxLen; + else + { + lenLimit = _streamPos - _pos; + if(lenLimit < kMinMatchCheck) + { + RINOK(MovePos()); + continue; + } + } + UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; + #endif + const Byte *cur = _buffer + _pos; + + #ifdef HASH_ARRAY_2 + UInt32 hash2Value; + #ifdef HASH_ARRAY_3 + UInt32 hash3Value; + UInt32 hashValue; + HASH_CALC; + _hash[kHash3Offset + hash3Value] = _pos; + #else + UInt32 hashValue; + HASH_CALC; + #endif + _hash[hash2Value] = _pos; + #else + UInt32 hashValue = Hash(cur); + #endif + + UInt32 curMatch = _hash[kFixHashSize + hashValue]; + _hash[kFixHashSize + hashValue] = _pos; + + #ifdef _HASH_CHAIN + _son[_cyclicBufferPos] = curMatch; + #else + CIndex *son = _son; + CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1; + CIndex *ptr1 = son + (_cyclicBufferPos << 1); + + UInt32 len0, len1; + len0 = len1 = kNumHashDirectBytes; + UInt32 count = _cutValue; + while(true) + { + if(curMatch <= matchMinPos || count-- == 0) + { + *ptr0 = *ptr1 = kEmptyHashValue; + break; + } + + UInt32 delta = _pos - curMatch; + UInt32 cyclicPos = (delta <= _cyclicBufferPos) ? + (_cyclicBufferPos - delta): + (_cyclicBufferPos - delta + _cyclicBufferSize); + CIndex *pair = son + (cyclicPos << 1); + + // _mm_prefetch((const char *)pair, _MM_HINT_T0); + + const Byte *pb = _buffer + curMatch; + UInt32 len = MyMin(len0, len1); + + if (pb[len] == cur[len]) + { + while(++len != lenLimit) + if (pb[len] != cur[len]) + break; + if (len == lenLimit) + { + *ptr1 = pair[0]; + *ptr0 = pair[1]; + break; + } + } + if (pb[len] < cur[len]) + { + *ptr1 = curMatch; + ptr1 = pair + 1; + curMatch = *ptr1; + len1 = len; + } + else + { + *ptr0 = curMatch; + ptr0 = pair; + curMatch = *ptr0; + len0 = len; + } + } + #endif + if (++_cyclicBufferPos == _cyclicBufferSize) + _cyclicBufferPos = 0; + RINOK(CLZInWindow::MovePos()); + if (_pos == kMaxValForNormalize) + Normalize(); + } + while(--num != 0); + return S_OK; +} + +void CMatchFinder::Normalize() +{ + UInt32 subValue = _pos - _cyclicBufferSize; + CIndex *items = _hash; + UInt32 numItems = (_hashSizeSum + _cyclicBufferSize + #ifndef _HASH_CHAIN + * 2 + #endif + ); + for (UInt32 i = 0; i < numItems; i++) + { + UInt32 value = items[i]; + if (value <= subValue) + value = kEmptyHashValue; + else + value -= subValue; + items[i] = value; + } + ReduceOffsets(subValue); +} + +HRESULT CMatchFinder::MovePos() +{ + if (++_cyclicBufferPos == _cyclicBufferSize) + _cyclicBufferPos = 0; + RINOK(CLZInWindow::MovePos()); + if (_pos == kMaxValForNormalize) + Normalize(); + return S_OK; +} + +STDMETHODIMP_(Byte) CMatchFinder::GetIndexByte(Int32 index) + { return CLZInWindow::GetIndexByte(index); } + +STDMETHODIMP_(UInt32) CMatchFinder::GetMatchLen(Int32 index, + UInt32 back, UInt32 limit) + { return CLZInWindow::GetMatchLen(index, back, limit); } + +STDMETHODIMP_(UInt32) CMatchFinder::GetNumAvailableBytes() + { return CLZInWindow::GetNumAvailableBytes(); } + +STDMETHODIMP_(const Byte *) CMatchFinder::GetPointerToCurrentPos() + { return CLZInWindow::GetPointerToCurrentPos(); } + +STDMETHODIMP_(Int32) CMatchFinder::NeedChangeBufferPos(UInt32 numCheckBytes) + { return CLZInWindow::NeedMove(numCheckBytes) ? 1: 0; } + +STDMETHODIMP_(void) CMatchFinder::ChangeBufferPos() + { CLZInWindow::MoveBlock();} + +#undef HASH_CALC +#undef kNumHashDirectBytes + +} diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/HashChain/HC4.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/HashChain/HC4.h new file mode 100644 index 0000000000..1fda4ac6ba --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/HashChain/HC4.h @@ -0,0 +1,19 @@ +// HC4.h + +#ifndef __HC4_H +#define __HC4_H + +#define BT_NAMESPACE NHC4 + +#define HASH_ARRAY_2 +#define HASH_ARRAY_3 + +#include "HCMain.h" + +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 + +#undef BT_NAMESPACE + +#endif + diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h new file mode 100644 index 0000000000..d509befea0 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h @@ -0,0 +1,6 @@ +// HCMain.h + +#define _HASH_CHAIN +#include "../BinTree/BinTreeMain.h" +#undef _HASH_CHAIN + diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/IMatchFinder.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/IMatchFinder.h new file mode 100644 index 0000000000..8b8480b2d2 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/IMatchFinder.h @@ -0,0 +1,33 @@ +// MatchFinders/IMatchFinder.h + +#ifndef __IMATCHFINDER_H +#define __IMATCHFINDER_H + +struct IInWindowStream: public IUnknown +{ + STDMETHOD(SetStream)(ISequentialInStream *inStream) PURE; + STDMETHOD_(void, ReleaseStream)() PURE; + STDMETHOD(Init)() PURE; + STDMETHOD_(Byte, GetIndexByte)(Int32 index) PURE; + STDMETHOD_(UInt32, GetMatchLen)(Int32 index, UInt32 distance, UInt32 limit) PURE; + STDMETHOD_(UInt32, GetNumAvailableBytes)() PURE; + STDMETHOD_(const Byte *, GetPointerToCurrentPos)() PURE; + STDMETHOD_(Int32, NeedChangeBufferPos)(UInt32 numCheckBytes) PURE; + STDMETHOD_(void, ChangeBufferPos)() PURE; +}; + +struct IMatchFinder: public IInWindowStream +{ + STDMETHOD(Create)(UInt32 historySize, UInt32 keepAddBufferBefore, + UInt32 matchMaxLen, UInt32 keepAddBufferAfter) PURE; + STDMETHOD(GetMatches)(UInt32 *distances) PURE; + STDMETHOD(Skip)(UInt32 num) PURE; +}; + +struct IMatchFinderSetNumPasses +{ + virtual ~IMatchFinderSetNumPasses(){} + virtual void SetNumPasses(UInt32 numPasses) PURE; +}; + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/LZInWindow.cpp b/util/cbfstool/lzma/C/7zip/Compress/LZ/LZInWindow.cpp new file mode 100644 index 0000000000..0e65c4254b --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/LZInWindow.cpp @@ -0,0 +1,105 @@ +// LZInWindow.cpp + +#include "StdAfx.h" + +#include "LZInWindow.h" +#include "../../../Common/MyCom.h" +#include "../../../Common/Alloc.h" + +void CLZInWindow::Free() +{ + ::BigFree(_bufferBase); + _bufferBase = 0; +} + +bool CLZInWindow::Create(UInt32 keepSizeBefore, UInt32 keepSizeAfter, UInt32 keepSizeReserv) +{ + _keepSizeBefore = keepSizeBefore; + _keepSizeAfter = keepSizeAfter; + UInt32 blockSize = keepSizeBefore + keepSizeAfter + keepSizeReserv; + if (_bufferBase == 0 || _blockSize != blockSize) + { + Free(); + _blockSize = blockSize; + if (_blockSize != 0) + _bufferBase = (Byte *)::BigAlloc(_blockSize); + } + _pointerToLastSafePosition = _bufferBase + _blockSize - keepSizeAfter; + if (_blockSize == 0) + return true; + return (_bufferBase != 0); +} + +void CLZInWindow::SetStream(ISequentialInStream *stream) +{ + _stream = stream; +} + +HRESULT CLZInWindow::Init() +{ + _buffer = _bufferBase; + _pos = 0; + _streamPos = 0; + _streamEndWasReached = false; + return ReadBlock(); +} + +/* +void CLZInWindow::ReleaseStream() +{ + _stream.Release(); +} +*/ + +/////////////////////////////////////////// +// ReadBlock + +// In State: +// (_buffer + _streamPos) <= (_bufferBase + _blockSize) +// Out State: +// _posLimit <= _blockSize - _keepSizeAfter; +// if(_streamEndWasReached == false): +// _streamPos >= _pos + _keepSizeAfter +// _posLimit = _streamPos - _keepSizeAfter; +// else +// + +HRESULT CLZInWindow::ReadBlock() +{ + if(_streamEndWasReached) + return S_OK; + while(true) + { + UInt32 size = (UInt32)(_bufferBase - _buffer) + _blockSize - _streamPos; + if(size == 0) + return S_OK; + UInt32 numReadBytes; + RINOK(_stream->Read(_buffer + _streamPos, size, &numReadBytes)); + if(numReadBytes == 0) + { + _posLimit = _streamPos; + const Byte *pointerToPostion = _buffer + _posLimit; + if(pointerToPostion > _pointerToLastSafePosition) + _posLimit = (UInt32)(_pointerToLastSafePosition - _buffer); + _streamEndWasReached = true; + return S_OK; + } + _streamPos += numReadBytes; + if(_streamPos >= _pos + _keepSizeAfter) + { + _posLimit = _streamPos - _keepSizeAfter; + return S_OK; + } + } +} + +void CLZInWindow::MoveBlock() +{ + UInt32 offset = (UInt32)(_buffer - _bufferBase) + _pos - _keepSizeBefore; + // we need one additional byte, since MovePos moves on 1 byte. + if (offset > 0) + offset--; + UInt32 numBytes = (UInt32)(_buffer - _bufferBase) + _streamPos - offset; + memmove(_bufferBase, _bufferBase + offset, numBytes); + _buffer -= offset; +} diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/LZInWindow.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/LZInWindow.h new file mode 100644 index 0000000000..54f2cb7bba --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/LZInWindow.h @@ -0,0 +1,87 @@ +// LZInWindow.h + +#ifndef __LZ_IN_WINDOW_H +#define __LZ_IN_WINDOW_H + +#include "../../IStream.h" + +class CLZInWindow +{ + Byte *_bufferBase; // pointer to buffer with data + ISequentialInStream *_stream; + UInt32 _posLimit; // offset (from _buffer) when new block reading must be done + bool _streamEndWasReached; // if (true) then _streamPos shows real end of stream + const Byte *_pointerToLastSafePosition; +protected: + Byte *_buffer; // Pointer to virtual Buffer begin + UInt32 _blockSize; // Size of Allocated memory block + UInt32 _pos; // offset (from _buffer) of curent byte + UInt32 _keepSizeBefore; // how many BYTEs must be kept in buffer before _pos + UInt32 _keepSizeAfter; // how many BYTEs must be kept buffer after _pos + UInt32 _streamPos; // offset (from _buffer) of first not read byte from Stream + + void MoveBlock(); + HRESULT ReadBlock(); + void Free(); +public: + CLZInWindow(): _bufferBase(0) {} + virtual ~CLZInWindow() { Free(); } + + // keepSizeBefore + keepSizeAfter + keepSizeReserv < 4G) + bool Create(UInt32 keepSizeBefore, UInt32 keepSizeAfter, UInt32 keepSizeReserv = (1<<17)); + + void SetStream(ISequentialInStream *stream); + HRESULT Init(); + // void ReleaseStream(); + + Byte *GetBuffer() const { return _buffer; } + + const Byte *GetPointerToCurrentPos() const { return _buffer + _pos; } + + HRESULT MovePos() + { + _pos++; + if (_pos > _posLimit) + { + const Byte *pointerToPostion = _buffer + _pos; + if(pointerToPostion > _pointerToLastSafePosition) + MoveBlock(); + return ReadBlock(); + } + else + return S_OK; + } + Byte GetIndexByte(Int32 index) const { return _buffer[(size_t)_pos + index]; } + + // index + limit have not to exceed _keepSizeAfter; + // -2G <= index < 2G + UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit) const + { + if(_streamEndWasReached) + if ((_pos + index) + limit > _streamPos) + limit = _streamPos - (_pos + index); + distance++; + const Byte *pby = _buffer + (size_t)_pos + index; + UInt32 i; + for(i = 0; i < limit && pby[i] == pby[(size_t)i - distance]; i++); + return i; + } + + UInt32 GetNumAvailableBytes() const { return _streamPos - _pos; } + + void ReduceOffsets(Int32 subValue) + { + _buffer += subValue; + _posLimit -= subValue; + _pos -= subValue; + _streamPos -= subValue; + } + + bool NeedMove(UInt32 numCheckBytes) + { + UInt32 reserv = _pointerToLastSafePosition - (_buffer + _pos); + return (reserv <= numCheckBytes); + } +}; + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZ/StdAfx.h b/util/cbfstool/lzma/C/7zip/Compress/LZ/StdAfx.h new file mode 100644 index 0000000000..3ff6d8a29f --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZ/StdAfx.h @@ -0,0 +1,6 @@ +// StdAfx.h + +#ifndef __STDAFX_H +#define __STDAFX_H + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMA.h b/util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMA.h new file mode 100644 index 0000000000..7bc4c438af --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMA.h @@ -0,0 +1,82 @@ +// LZMA.h + +#ifndef __LZMA_H +#define __LZMA_H + +namespace NCompress { +namespace NLZMA { + +const UInt32 kNumRepDistances = 4; + +const int 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 Index; + void Init() { Index = 0; } + void UpdateChar() { Index = kLiteralNextStates[Index]; } + void UpdateMatch() { Index = kMatchNextStates[Index]; } + void UpdateRep() { Index = kRepNextStates[Index]; } + void UpdateShortRep() { Index = kShortRepNextStates[Index]; } + bool IsCharState() const { return Index < 7; } +}; + +const int kNumPosSlotBits = 6; +const int kDicLogSizeMin = 0; +const int kDicLogSizeMax = 32; +const int kDistTableSizeMax = kDicLogSizeMax * 2; + +const UInt32 kNumLenToPosStates = 4; + +inline UInt32 GetLenToPosState(UInt32 len) +{ + len -= 2; + if (len < kNumLenToPosStates) + return len; + return kNumLenToPosStates - 1; +} + +namespace NLength { + +const int kNumPosStatesBitsMax = 4; +const UInt32 kNumPosStatesMax = (1 << kNumPosStatesBitsMax); + +const int kNumPosStatesBitsEncodingMax = 4; +const UInt32 kNumPosStatesEncodingMax = (1 << kNumPosStatesBitsEncodingMax); + +const int kNumLowBits = 3; +const int kNumMidBits = 3; +const int kNumHighBits = 8; +const UInt32 kNumLowSymbols = 1 << kNumLowBits; +const UInt32 kNumMidSymbols = 1 << kNumMidBits; +const UInt32 kNumSymbolsTotal = kNumLowSymbols + kNumMidSymbols + (1 << kNumHighBits); + +} + +const UInt32 kMatchMinLen = 2; +const UInt32 kMatchMaxLen = kMatchMinLen + NLength::kNumSymbolsTotal - 1; + +const int kNumAlignBits = 4; +const UInt32 kAlignTableSize = 1 << kNumAlignBits; +const UInt32 kAlignMask = (kAlignTableSize - 1); + +const UInt32 kStartPosModelIndex = 4; +const UInt32 kEndPosModelIndex = 14; +const UInt32 kNumPosModels = kEndPosModelIndex - kStartPosModelIndex; + +const UInt32 kNumFullDistances = 1 << (kEndPosModelIndex / 2); + +const int kNumLitPosStatesBitsEncodingMax = 4; +const int kNumLitContextBitsMax = 8; + +const int kNumMoveBits = 5; + +}} + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp b/util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp new file mode 100644 index 0000000000..8d8f0a004c --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp @@ -0,0 +1,1564 @@ +// LZMA/Encoder.cpp + +#include "StdAfx.h" + +#include "../../../Common/Defs.h" +#include "../../Common/StreamUtils.h" + +#include "LZMAEncoder.h" + +// for minimal compressing code size define these: +// #define COMPRESS_MF_BT +// #define COMPRESS_MF_BT4 + +#if !defined(COMPRESS_MF_BT) && !defined(COMPRESS_MF_HC) +#define COMPRESS_MF_BT +#define COMPRESS_MF_HC +#endif + +#ifdef COMPRESS_MF_BT +#if !defined(COMPRESS_MF_BT2) && !defined(COMPRESS_MF_BT3) && !defined(COMPRESS_MF_BT4) +#define COMPRESS_MF_BT2 +#define COMPRESS_MF_BT3 +#define COMPRESS_MF_BT4 +#endif +#ifdef COMPRESS_MF_BT2 +#include "../LZ/BinTree/BinTree2.h" +#endif +#ifdef COMPRESS_MF_BT3 +#include "../LZ/BinTree/BinTree3.h" +#endif +#ifdef COMPRESS_MF_BT4 +#include "../LZ/BinTree/BinTree4.h" +#endif +#endif + +#ifdef COMPRESS_MF_HC +#include "../LZ/HashChain/HC4.h" +#endif + +#ifdef COMPRESS_MF_MT +#include "../LZ/MT/MT.h" +#endif + +namespace NCompress { +namespace NLZMA { + +const int kDefaultDictionaryLogSize = 22; +const UInt32 kNumFastBytesDefault = 0x20; + +enum +{ + kBT2, + kBT3, + kBT4, + kHC4 +}; + +static const wchar_t *kMatchFinderIDs[] = +{ + L"BT2", + L"BT3", + L"BT4", + L"HC4" +}; + +Byte g_FastPos[1 << 11]; + +class CFastPosInit +{ +public: + CFastPosInit() { Init(); } + void Init() + { + const Byte kFastSlots = 22; + int c = 2; + g_FastPos[0] = 0; + g_FastPos[1] = 1; + + for (Byte slotFast = 2; slotFast < kFastSlots; slotFast++) + { + UInt32 k = (1 << ((slotFast >> 1) - 1)); + for (UInt32 j = 0; j < k; j++, c++) + g_FastPos[c] = slotFast; + } + } +} g_FastPosInit; + + +void CLiteralEncoder2::Encode(NRangeCoder::CEncoder *rangeEncoder, Byte symbol) +{ + UInt32 context = 1; + int i = 8; + do + { + i--; + UInt32 bit = (symbol >> i) & 1; + _encoders[context].Encode(rangeEncoder, bit); + context = (context << 1) | bit; + } + while(i != 0); +} + +void CLiteralEncoder2::EncodeMatched(NRangeCoder::CEncoder *rangeEncoder, + Byte matchByte, Byte symbol) +{ + UInt32 context = 1; + int i = 8; + do + { + i--; + UInt32 bit = (symbol >> i) & 1; + UInt32 matchBit = (matchByte >> i) & 1; + _encoders[0x100 + (matchBit << 8) + context].Encode(rangeEncoder, bit); + context = (context << 1) | bit; + if (matchBit != bit) + { + while(i != 0) + { + i--; + UInt32 bit = (symbol >> i) & 1; + _encoders[context].Encode(rangeEncoder, bit); + context = (context << 1) | bit; + } + break; + } + } + while(i != 0); +} + +UInt32 CLiteralEncoder2::GetPrice(bool matchMode, Byte matchByte, Byte symbol) const +{ + UInt32 price = 0; + UInt32 context = 1; + int i = 8; + if (matchMode) + { + do + { + i--; + UInt32 matchBit = (matchByte >> i) & 1; + UInt32 bit = (symbol >> i) & 1; + price += _encoders[0x100 + (matchBit << 8) + context].GetPrice(bit); + context = (context << 1) | bit; + if (matchBit != bit) + break; + } + while (i != 0); + } + while(i != 0) + { + i--; + UInt32 bit = (symbol >> i) & 1; + price += _encoders[context].GetPrice(bit); + context = (context << 1) | bit; + } + return price; +}; + + +namespace NLength { + +void CEncoder::Init(UInt32 numPosStates) +{ + _choice.Init(); + _choice2.Init(); + for (UInt32 posState = 0; posState < numPosStates; posState++) + { + _lowCoder[posState].Init(); + _midCoder[posState].Init(); + } + _highCoder.Init(); +} + +void CEncoder::Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState) +{ + if(symbol < kNumLowSymbols) + { + _choice.Encode(rangeEncoder, 0); + _lowCoder[posState].Encode(rangeEncoder, symbol); + } + else + { + _choice.Encode(rangeEncoder, 1); + if(symbol < kNumLowSymbols + kNumMidSymbols) + { + _choice2.Encode(rangeEncoder, 0); + _midCoder[posState].Encode(rangeEncoder, symbol - kNumLowSymbols); + } + else + { + _choice2.Encode(rangeEncoder, 1); + _highCoder.Encode(rangeEncoder, symbol - kNumLowSymbols - kNumMidSymbols); + } + } +} + +void CEncoder::SetPrices(UInt32 posState, UInt32 numSymbols, UInt32 *prices) const +{ + UInt32 a0 = _choice.GetPrice0(); + UInt32 a1 = _choice.GetPrice1(); + UInt32 b0 = a1 + _choice2.GetPrice0(); + UInt32 b1 = a1 + _choice2.GetPrice1(); + UInt32 i = 0; + for (i = 0; i < kNumLowSymbols; i++) + { + if (i >= numSymbols) + return; + prices[i] = a0 + _lowCoder[posState].GetPrice(i); + } + for (; i < kNumLowSymbols + kNumMidSymbols; i++) + { + if (i >= numSymbols) + return; + prices[i] = b0 + _midCoder[posState].GetPrice(i - kNumLowSymbols); + } + for (; i < numSymbols; i++) + prices[i] = b1 + _highCoder.GetPrice(i - kNumLowSymbols - kNumMidSymbols); +} + +} +CEncoder::CEncoder(): + _numFastBytes(kNumFastBytesDefault), + _distTableSize(kDefaultDictionaryLogSize * 2), + _posStateBits(2), + _posStateMask(4 - 1), + _numLiteralPosStateBits(0), + _numLiteralContextBits(3), + _dictionarySize(1 << kDefaultDictionaryLogSize), + _dictionarySizePrev(UInt32(-1)), + _numFastBytesPrev(UInt32(-1)), + _matchFinderCycles(0), + _matchFinderIndex(kBT4), + #ifdef COMPRESS_MF_MT + _multiThread(false), + #endif + _writeEndMark(false), + setMfPasses(0) +{ + // _maxMode = false; + _fastMode = false; +} + +HRESULT CEncoder::Create() +{ + if (!_rangeEncoder.Create(1 << 20)) + return E_OUTOFMEMORY; + if (!_matchFinder) + { + switch(_matchFinderIndex) + { + #ifdef COMPRESS_MF_BT + #ifdef COMPRESS_MF_BT2 + case kBT2: + { + NBT2::CMatchFinder *mfSpec = new NBT2::CMatchFinder; + setMfPasses = mfSpec; + _matchFinder = mfSpec; + break; + } + #endif + #ifdef COMPRESS_MF_BT3 + case kBT3: + { + NBT3::CMatchFinder *mfSpec = new NBT3::CMatchFinder; + setMfPasses = mfSpec; + _matchFinder = mfSpec; + break; + } + #endif + #ifdef COMPRESS_MF_BT4 + case kBT4: + { + NBT4::CMatchFinder *mfSpec = new NBT4::CMatchFinder; + setMfPasses = mfSpec; + _matchFinder = mfSpec; + break; + } + #endif + #endif + + #ifdef COMPRESS_MF_HC + case kHC4: + { + NHC4::CMatchFinder *mfSpec = new NHC4::CMatchFinder; + setMfPasses = mfSpec; + _matchFinder = mfSpec; + break; + } + #endif + } + if (_matchFinder == 0) + return E_OUTOFMEMORY; + + #ifdef COMPRESS_MF_MT + if (_multiThread && !(_fastMode && (_matchFinderIndex == kHC4))) + { + CMatchFinderMT *mfSpec = new CMatchFinderMT; + if (mfSpec == 0) + return E_OUTOFMEMORY; + CMyComPtr mf = mfSpec; + RINOK(mfSpec->SetMatchFinder(_matchFinder)); + _matchFinder.Release(); + _matchFinder = mf; + } + #endif + } + + if (!_literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits)) + return E_OUTOFMEMORY; + + if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes) + return S_OK; + RINOK(_matchFinder->Create(_dictionarySize, kNumOpts, _numFastBytes, kMatchMaxLen + 1)); // actually it's + _numFastBytes - _numFastBytes + if (_matchFinderCycles != 0 && setMfPasses != 0) + setMfPasses->SetNumPasses(_matchFinderCycles); + _dictionarySizePrev = _dictionarySize; + _numFastBytesPrev = _numFastBytes; + return S_OK; +} + +static bool AreStringsEqual(const wchar_t *base, const wchar_t *testString) +{ + while (true) + { + wchar_t c = *testString; + if (c >= 'a' && c <= 'z') + c -= 0x20; + if (*base != c) + return false; + if (c == 0) + return true; + base++; + testString++; + } +} + +static int FindMatchFinder(const wchar_t *s) +{ + for (int m = 0; m < (int)(sizeof(kMatchFinderIDs) / sizeof(kMatchFinderIDs[0])); m++) + if (AreStringsEqual(kMatchFinderIDs[m], s)) + return m; + return -1; +} + +STDMETHODIMP CEncoder::SetCoderProperties(const PROPID *propIDs, + const PROPVARIANT *properties, UInt32 numProperties) +{ + for (UInt32 i = 0; i < numProperties; i++) + { + const PROPVARIANT &prop = properties[i]; + switch(propIDs[i]) + { + case NCoderPropID::kNumFastBytes: + { + if (prop.vt != VT_UI4) + return E_INVALIDARG; + UInt32 numFastBytes = prop.ulVal; + if(numFastBytes < 5 || numFastBytes > kMatchMaxLen) + return E_INVALIDARG; + _numFastBytes = numFastBytes; + break; + } + case NCoderPropID::kMatchFinderCycles: + { + if (prop.vt != VT_UI4) + return E_INVALIDARG; + _matchFinderCycles = prop.ulVal; + break; + } + case NCoderPropID::kAlgorithm: + { + if (prop.vt != VT_UI4) + return E_INVALIDARG; + UInt32 maximize = prop.ulVal; + _fastMode = (maximize == 0); + // _maxMode = (maximize >= 2); + break; + } + case NCoderPropID::kMatchFinder: + { + if (prop.vt != VT_BSTR) + return E_INVALIDARG; + int matchFinderIndexPrev = _matchFinderIndex; + int m = FindMatchFinder(prop.bstrVal); + if (m < 0) + return E_INVALIDARG; + _matchFinderIndex = m; + if (_matchFinder && matchFinderIndexPrev != _matchFinderIndex) + { + _dictionarySizePrev = (UInt32)-1; + ReleaseMatchFinder(); + } + break; + } + #ifdef COMPRESS_MF_MT + case NCoderPropID::kMultiThread: + { + if (prop.vt != VT_BOOL) + return E_INVALIDARG; + bool newMultiThread = (prop.boolVal == VARIANT_TRUE); + if (newMultiThread != _multiThread) + { + _dictionarySizePrev = (UInt32)-1; + ReleaseMatchFinder(); + _multiThread = newMultiThread; + } + break; + } + case NCoderPropID::kNumThreads: + { + if (prop.vt != VT_UI4) + return E_INVALIDARG; + bool newMultiThread = (prop.ulVal > 1); + if (newMultiThread != _multiThread) + { + _dictionarySizePrev = (UInt32)-1; + ReleaseMatchFinder(); + _multiThread = newMultiThread; + } + break; + } + #endif + case NCoderPropID::kDictionarySize: + { + const int kDicLogSizeMaxCompress = 30; + if (prop.vt != VT_UI4) + return E_INVALIDARG; + UInt32 dictionarySize = prop.ulVal; + if (dictionarySize < UInt32(1 << kDicLogSizeMin) || + dictionarySize > UInt32(1 << kDicLogSizeMaxCompress)) + return E_INVALIDARG; + _dictionarySize = dictionarySize; + UInt32 dicLogSize; + for(dicLogSize = 0; dicLogSize < (UInt32)kDicLogSizeMaxCompress; dicLogSize++) + if (dictionarySize <= (UInt32(1) << dicLogSize)) + break; + _distTableSize = dicLogSize * 2; + break; + } + case NCoderPropID::kPosStateBits: + { + if (prop.vt != VT_UI4) + return E_INVALIDARG; + UInt32 value = prop.ulVal; + if (value > (UInt32)NLength::kNumPosStatesBitsEncodingMax) + return E_INVALIDARG; + _posStateBits = value; + _posStateMask = (1 << _posStateBits) - 1; + break; + } + case NCoderPropID::kLitPosBits: + { + if (prop.vt != VT_UI4) + return E_INVALIDARG; + UInt32 value = prop.ulVal; + if (value > (UInt32)kNumLitPosStatesBitsEncodingMax) + return E_INVALIDARG; + _numLiteralPosStateBits = value; + break; + } + case NCoderPropID::kLitContextBits: + { + if (prop.vt != VT_UI4) + return E_INVALIDARG; + UInt32 value = prop.ulVal; + if (value > (UInt32)kNumLitContextBitsMax) + return E_INVALIDARG; + _numLiteralContextBits = value; + break; + } + case NCoderPropID::kEndMarker: + { + if (prop.vt != VT_BOOL) + return E_INVALIDARG; + SetWriteEndMarkerMode(prop.boolVal == VARIANT_TRUE); + break; + } + default: + return E_INVALIDARG; + } + } + return S_OK; +} + +STDMETHODIMP CEncoder::WriteCoderProperties(ISequentialOutStream *outStream) +{ + const UInt32 kPropSize = 5; + Byte properties[kPropSize]; + properties[0] = (_posStateBits * 5 + _numLiteralPosStateBits) * 9 + _numLiteralContextBits; + for (int i = 0; i < 4; i++) + properties[1 + i] = Byte(_dictionarySize >> (8 * i)); + return WriteStream(outStream, properties, kPropSize, NULL); +} + +STDMETHODIMP CEncoder::SetOutStream(ISequentialOutStream *outStream) +{ + _rangeEncoder.SetStream(outStream); + return S_OK; +} + +STDMETHODIMP CEncoder::ReleaseOutStream() +{ + _rangeEncoder.ReleaseStream(); + return S_OK; +} + +HRESULT CEncoder::Init() +{ + CBaseState::Init(); + + // RINOK(_matchFinder->Init(inStream)); + _rangeEncoder.Init(); + + for(int i = 0; i < kNumStates; i++) + { + for (UInt32 j = 0; j <= _posStateMask; j++) + { + _isMatch[i][j].Init(); + _isRep0Long[i][j].Init(); + } + _isRep[i].Init(); + _isRepG0[i].Init(); + _isRepG1[i].Init(); + _isRepG2[i].Init(); + } + + _literalEncoder.Init(); + + { + for(UInt32 i = 0; i < kNumLenToPosStates; i++) + _posSlotEncoder[i].Init(); + } + { + for(UInt32 i = 0; i < kNumFullDistances - kEndPosModelIndex; i++) + _posEncoders[i].Init(); + } + + _lenEncoder.Init(1 << _posStateBits); + _repMatchLenEncoder.Init(1 << _posStateBits); + + _posAlignEncoder.Init(); + + _longestMatchWasFound = false; + _optimumEndIndex = 0; + _optimumCurrentIndex = 0; + _additionalOffset = 0; + + return S_OK; +} + +HRESULT CEncoder::MovePos(UInt32 num) +{ + if (num == 0) + return S_OK; + _additionalOffset += num; + return _matchFinder->Skip(num); +} + +UInt32 CEncoder::Backward(UInt32 &backRes, UInt32 cur) +{ + _optimumEndIndex = cur; + UInt32 posMem = _optimum[cur].PosPrev; + UInt32 backMem = _optimum[cur].BackPrev; + do + { + if (_optimum[cur].Prev1IsChar) + { + _optimum[posMem].MakeAsChar(); + _optimum[posMem].PosPrev = posMem - 1; + if (_optimum[cur].Prev2) + { + _optimum[posMem - 1].Prev1IsChar = false; + _optimum[posMem - 1].PosPrev = _optimum[cur].PosPrev2; + _optimum[posMem - 1].BackPrev = _optimum[cur].BackPrev2; + } + } + UInt32 posPrev = posMem; + UInt32 backCur = backMem; + + backMem = _optimum[posPrev].BackPrev; + posMem = _optimum[posPrev].PosPrev; + + _optimum[posPrev].BackPrev = backCur; + _optimum[posPrev].PosPrev = cur; + cur = posPrev; + } + while(cur != 0); + backRes = _optimum[0].BackPrev; + _optimumCurrentIndex = _optimum[0].PosPrev; + return _optimumCurrentIndex; +} + +/* +Out: + (lenRes == 1) && (backRes == 0xFFFFFFFF) means Literal +*/ + +HRESULT CEncoder::GetOptimum(UInt32 position, UInt32 &backRes, UInt32 &lenRes) +{ + if(_optimumEndIndex != _optimumCurrentIndex) + { + const COptimal &optimum = _optimum[_optimumCurrentIndex]; + lenRes = optimum.PosPrev - _optimumCurrentIndex; + backRes = optimum.BackPrev; + _optimumCurrentIndex = optimum.PosPrev; + return S_OK; + } + _optimumCurrentIndex = _optimumEndIndex = 0; + + UInt32 lenMain, numDistancePairs; + if (!_longestMatchWasFound) + { + RINOK(ReadMatchDistances(lenMain, numDistancePairs)); + } + else + { + lenMain = _longestMatchLength; + numDistancePairs = _numDistancePairs; + _longestMatchWasFound = false; + } + + const Byte *data = _matchFinder->GetPointerToCurrentPos() - 1; + UInt32 numAvailableBytes = _matchFinder->GetNumAvailableBytes() + 1; + if (numAvailableBytes < 2) + { + backRes = (UInt32)(-1); + lenRes = 1; + return S_OK; + } + if (numAvailableBytes > kMatchMaxLen) + numAvailableBytes = kMatchMaxLen; + + UInt32 reps[kNumRepDistances]; + UInt32 repLens[kNumRepDistances]; + UInt32 repMaxIndex = 0; + UInt32 i; + for(i = 0; i < kNumRepDistances; i++) + { + reps[i] = _repDistances[i]; + UInt32 backOffset = reps[i] + 1; + if (data[0] != data[(size_t)0 - backOffset] || data[1] != data[(size_t)1 - backOffset]) + { + repLens[i] = 0; + continue; + } + UInt32 lenTest; + for (lenTest = 2; lenTest < numAvailableBytes && + data[lenTest] == data[(size_t)lenTest - backOffset]; lenTest++); + repLens[i] = lenTest; + if (lenTest > repLens[repMaxIndex]) + repMaxIndex = i; + } + if(repLens[repMaxIndex] >= _numFastBytes) + { + backRes = repMaxIndex; + lenRes = repLens[repMaxIndex]; + return MovePos(lenRes - 1); + } + + UInt32 *matchDistances = _matchDistances + 1; + if(lenMain >= _numFastBytes) + { + backRes = matchDistances[numDistancePairs - 1] + kNumRepDistances; + lenRes = lenMain; + return MovePos(lenMain - 1); + } + Byte currentByte = *data; + Byte matchByte = data[(size_t)0 - reps[0] - 1]; + + if(lenMain < 2 && currentByte != matchByte && repLens[repMaxIndex] < 2) + { + backRes = (UInt32)-1; + lenRes = 1; + return S_OK; + } + + _optimum[0].State = _state; + + UInt32 posState = (position & _posStateMask); + + _optimum[1].Price = _isMatch[_state.Index][posState].GetPrice0() + + _literalEncoder.GetSubCoder(position, _previousByte)->GetPrice(!_state.IsCharState(), matchByte, currentByte); + _optimum[1].MakeAsChar(); + + UInt32 matchPrice = _isMatch[_state.Index][posState].GetPrice1(); + UInt32 repMatchPrice = matchPrice + _isRep[_state.Index].GetPrice1(); + + if(matchByte == currentByte) + { + UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState); + if(shortRepPrice < _optimum[1].Price) + { + _optimum[1].Price = shortRepPrice; + _optimum[1].MakeAsShortRep(); + } + } + UInt32 lenEnd = ((lenMain >= repLens[repMaxIndex]) ? lenMain : repLens[repMaxIndex]); + + if(lenEnd < 2) + { + backRes = _optimum[1].BackPrev; + lenRes = 1; + return S_OK; + } + + _optimum[1].PosPrev = 0; + for (i = 0; i < kNumRepDistances; i++) + _optimum[0].Backs[i] = reps[i]; + + UInt32 len = lenEnd; + do + _optimum[len--].Price = kIfinityPrice; + while (len >= 2); + + for(i = 0; i < kNumRepDistances; i++) + { + UInt32 repLen = repLens[i]; + if (repLen < 2) + continue; + UInt32 price = repMatchPrice + GetPureRepPrice(i, _state, posState); + do + { + UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(repLen - 2, posState); + COptimal &optimum = _optimum[repLen]; + if (curAndLenPrice < optimum.Price) + { + optimum.Price = curAndLenPrice; + optimum.PosPrev = 0; + optimum.BackPrev = i; + optimum.Prev1IsChar = false; + } + } + while(--repLen >= 2); + } + + UInt32 normalMatchPrice = matchPrice + _isRep[_state.Index].GetPrice0(); + + len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2); + if (len <= lenMain) + { + UInt32 offs = 0; + while (len > matchDistances[offs]) + offs += 2; + for(; ; len++) + { + UInt32 distance = matchDistances[offs + 1]; + UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(distance, len, posState); + COptimal &optimum = _optimum[len]; + if (curAndLenPrice < optimum.Price) + { + optimum.Price = curAndLenPrice; + optimum.PosPrev = 0; + optimum.BackPrev = distance + kNumRepDistances; + optimum.Prev1IsChar = false; + } + if (len == matchDistances[offs]) + { + offs += 2; + if (offs == numDistancePairs) + break; + } + } + } + + UInt32 cur = 0; + + while(true) + { + cur++; + if(cur == lenEnd) + { + lenRes = Backward(backRes, cur); + return S_OK; + } + UInt32 newLen, numDistancePairs; + RINOK(ReadMatchDistances(newLen, numDistancePairs)); + if(newLen >= _numFastBytes) + { + _numDistancePairs = numDistancePairs; + _longestMatchLength = newLen; + _longestMatchWasFound = true; + lenRes = Backward(backRes, cur); + return S_OK; + } + position++; + COptimal &curOptimum = _optimum[cur]; + UInt32 posPrev = curOptimum.PosPrev; + CState state; + if (curOptimum.Prev1IsChar) + { + posPrev--; + if (curOptimum.Prev2) + { + state = _optimum[curOptimum.PosPrev2].State; + if (curOptimum.BackPrev2 < kNumRepDistances) + state.UpdateRep(); + else + state.UpdateMatch(); + } + else + state = _optimum[posPrev].State; + state.UpdateChar(); + } + else + state = _optimum[posPrev].State; + if (posPrev == cur - 1) + { + if (curOptimum.IsShortRep()) + state.UpdateShortRep(); + else + state.UpdateChar(); + } + else + { + UInt32 pos; + if (curOptimum.Prev1IsChar && curOptimum.Prev2) + { + posPrev = curOptimum.PosPrev2; + pos = curOptimum.BackPrev2; + state.UpdateRep(); + } + else + { + pos = curOptimum.BackPrev; + if (pos < kNumRepDistances) + state.UpdateRep(); + else + state.UpdateMatch(); + } + const COptimal &prevOptimum = _optimum[posPrev]; + if (pos < kNumRepDistances) + { + reps[0] = prevOptimum.Backs[pos]; + UInt32 i; + for(i = 1; i <= pos; i++) + reps[i] = prevOptimum.Backs[i - 1]; + for(; i < kNumRepDistances; i++) + reps[i] = prevOptimum.Backs[i]; + } + else + { + reps[0] = (pos - kNumRepDistances); + for(UInt32 i = 1; i < kNumRepDistances; i++) + reps[i] = prevOptimum.Backs[i - 1]; + } + } + curOptimum.State = state; + for(UInt32 i = 0; i < kNumRepDistances; i++) + curOptimum.Backs[i] = reps[i]; + UInt32 curPrice = curOptimum.Price; + const Byte *data = _matchFinder->GetPointerToCurrentPos() - 1; + const Byte currentByte = *data; + const Byte matchByte = data[(size_t)0 - reps[0] - 1]; + + UInt32 posState = (position & _posStateMask); + + UInt32 curAnd1Price = curPrice + + _isMatch[state.Index][posState].GetPrice0() + + _literalEncoder.GetSubCoder(position, data[(size_t)0 - 1])->GetPrice(!state.IsCharState(), matchByte, currentByte); + + COptimal &nextOptimum = _optimum[cur + 1]; + + bool nextIsChar = false; + if (curAnd1Price < nextOptimum.Price) + { + nextOptimum.Price = curAnd1Price; + nextOptimum.PosPrev = cur; + nextOptimum.MakeAsChar(); + nextIsChar = true; + } + + UInt32 matchPrice = curPrice + _isMatch[state.Index][posState].GetPrice1(); + UInt32 repMatchPrice = matchPrice + _isRep[state.Index].GetPrice1(); + + if(matchByte == currentByte && + !(nextOptimum.PosPrev < cur && nextOptimum.BackPrev == 0)) + { + UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(state, posState); + if(shortRepPrice <= nextOptimum.Price) + { + nextOptimum.Price = shortRepPrice; + nextOptimum.PosPrev = cur; + nextOptimum.MakeAsShortRep(); + nextIsChar = true; + } + } + /* + if(newLen == 2 && matchDistances[2] >= kDistLimit2) // test it maybe set 2000 ? + continue; + */ + + UInt32 numAvailableBytesFull = _matchFinder->GetNumAvailableBytes() + 1; + numAvailableBytesFull = MyMin(kNumOpts - 1 - cur, numAvailableBytesFull); + UInt32 numAvailableBytes = numAvailableBytesFull; + + if (numAvailableBytes < 2) + continue; + if (numAvailableBytes > _numFastBytes) + numAvailableBytes = _numFastBytes; + if (!nextIsChar && matchByte != currentByte) // speed optimization + { + // try Literal + rep0 + UInt32 backOffset = reps[0] + 1; + UInt32 limit = MyMin(numAvailableBytesFull, _numFastBytes + 1); + UInt32 temp; + for (temp = 1; temp < limit && + data[temp] == data[(size_t)temp - backOffset]; temp++); + UInt32 lenTest2 = temp - 1; + if (lenTest2 >= 2) + { + CState state2 = state; + state2.UpdateChar(); + UInt32 posStateNext = (position + 1) & _posStateMask; + UInt32 nextRepMatchPrice = curAnd1Price + + _isMatch[state2.Index][posStateNext].GetPrice1() + + _isRep[state2.Index].GetPrice1(); + // for (; lenTest2 >= 2; lenTest2--) + { + UInt32 offset = cur + 1 + lenTest2; + while(lenEnd < offset) + _optimum[++lenEnd].Price = kIfinityPrice; + UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice( + 0, lenTest2, state2, posStateNext); + COptimal &optimum = _optimum[offset]; + if (curAndLenPrice < optimum.Price) + { + optimum.Price = curAndLenPrice; + optimum.PosPrev = cur + 1; + optimum.BackPrev = 0; + optimum.Prev1IsChar = true; + optimum.Prev2 = false; + } + } + } + } + + UInt32 startLen = 2; // speed optimization + for(UInt32 repIndex = 0; repIndex < kNumRepDistances; repIndex++) + { + // UInt32 repLen = _matchFinder->GetMatchLen(0 - 1, reps[repIndex], newLen); // test it; + UInt32 backOffset = reps[repIndex] + 1; + if (data[0] != data[(size_t)0 - backOffset] || + data[1] != data[(size_t)1 - backOffset]) + continue; + UInt32 lenTest; + for (lenTest = 2; lenTest < numAvailableBytes && + data[lenTest] == data[(size_t)lenTest - backOffset]; lenTest++); + while(lenEnd < cur + lenTest) + _optimum[++lenEnd].Price = kIfinityPrice; + UInt32 lenTestTemp = lenTest; + UInt32 price = repMatchPrice + GetPureRepPrice(repIndex, state, posState); + do + { + UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(lenTest - 2, posState); + COptimal &optimum = _optimum[cur + lenTest]; + if (curAndLenPrice < optimum.Price) + { + optimum.Price = curAndLenPrice; + optimum.PosPrev = cur; + optimum.BackPrev = repIndex; + optimum.Prev1IsChar = false; + } + } + while(--lenTest >= 2); + lenTest = lenTestTemp; + + if (repIndex == 0) + startLen = lenTest + 1; + + // if (_maxMode) + { + UInt32 lenTest2 = lenTest + 1; + UInt32 limit = MyMin(numAvailableBytesFull, lenTest2 + _numFastBytes); + for (; lenTest2 < limit && + data[lenTest2] == data[(size_t)lenTest2 - backOffset]; lenTest2++); + lenTest2 -= lenTest + 1; + if (lenTest2 >= 2) + { + CState state2 = state; + state2.UpdateRep(); + UInt32 posStateNext = (position + lenTest) & _posStateMask; + UInt32 curAndLenCharPrice = + price + _repMatchLenEncoder.GetPrice(lenTest - 2, posState) + + _isMatch[state2.Index][posStateNext].GetPrice0() + + _literalEncoder.GetSubCoder(position + lenTest, data[(size_t)lenTest - 1])->GetPrice( + true, data[(size_t)lenTest - backOffset], data[lenTest]); + state2.UpdateChar(); + posStateNext = (position + lenTest + 1) & _posStateMask; + UInt32 nextRepMatchPrice = curAndLenCharPrice + + _isMatch[state2.Index][posStateNext].GetPrice1() + + _isRep[state2.Index].GetPrice1(); + + // for(; lenTest2 >= 2; lenTest2--) + { + UInt32 offset = cur + lenTest + 1 + lenTest2; + while(lenEnd < offset) + _optimum[++lenEnd].Price = kIfinityPrice; + UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice( + 0, lenTest2, state2, posStateNext); + COptimal &optimum = _optimum[offset]; + if (curAndLenPrice < optimum.Price) + { + optimum.Price = curAndLenPrice; + optimum.PosPrev = cur + lenTest + 1; + optimum.BackPrev = 0; + optimum.Prev1IsChar = true; + optimum.Prev2 = true; + optimum.PosPrev2 = cur; + optimum.BackPrev2 = repIndex; + } + } + } + } + } + + // for(UInt32 lenTest = 2; lenTest <= newLen; lenTest++) + if (newLen > numAvailableBytes) + { + newLen = numAvailableBytes; + for (numDistancePairs = 0; newLen > matchDistances[numDistancePairs]; numDistancePairs += 2); + matchDistances[numDistancePairs] = newLen; + numDistancePairs += 2; + } + if (newLen >= startLen) + { + UInt32 normalMatchPrice = matchPrice + _isRep[state.Index].GetPrice0(); + while(lenEnd < cur + newLen) + _optimum[++lenEnd].Price = kIfinityPrice; + + UInt32 offs = 0; + while(startLen > matchDistances[offs]) + offs += 2; + UInt32 curBack = matchDistances[offs + 1]; + UInt32 posSlot = GetPosSlot2(curBack); + for(UInt32 lenTest = /*2*/ startLen; ; lenTest++) + { + UInt32 curAndLenPrice = normalMatchPrice; + UInt32 lenToPosState = GetLenToPosState(lenTest); + if (curBack < kNumFullDistances) + curAndLenPrice += _distancesPrices[lenToPosState][curBack]; + else + curAndLenPrice += _posSlotPrices[lenToPosState][posSlot] + _alignPrices[curBack & kAlignMask]; + + curAndLenPrice += _lenEncoder.GetPrice(lenTest - kMatchMinLen, posState); + + COptimal &optimum = _optimum[cur + lenTest]; + if (curAndLenPrice < optimum.Price) + { + optimum.Price = curAndLenPrice; + optimum.PosPrev = cur; + optimum.BackPrev = curBack + kNumRepDistances; + optimum.Prev1IsChar = false; + } + + if (/*_maxMode && */lenTest == matchDistances[offs]) + { + // Try Match + Literal + Rep0 + UInt32 backOffset = curBack + 1; + UInt32 lenTest2 = lenTest + 1; + UInt32 limit = MyMin(numAvailableBytesFull, lenTest2 + _numFastBytes); + for (; lenTest2 < limit && + data[lenTest2] == data[(size_t)lenTest2 - backOffset]; lenTest2++); + lenTest2 -= lenTest + 1; + if (lenTest2 >= 2) + { + CState state2 = state; + state2.UpdateMatch(); + UInt32 posStateNext = (position + lenTest) & _posStateMask; + UInt32 curAndLenCharPrice = curAndLenPrice + + _isMatch[state2.Index][posStateNext].GetPrice0() + + _literalEncoder.GetSubCoder(position + lenTest, data[(size_t)lenTest - 1])->GetPrice( + true, data[(size_t)lenTest - backOffset], data[lenTest]); + state2.UpdateChar(); + posStateNext = (posStateNext + 1) & _posStateMask; + UInt32 nextRepMatchPrice = curAndLenCharPrice + + _isMatch[state2.Index][posStateNext].GetPrice1() + + _isRep[state2.Index].GetPrice1(); + + // for(; lenTest2 >= 2; lenTest2--) + { + UInt32 offset = cur + lenTest + 1 + lenTest2; + while(lenEnd < offset) + _optimum[++lenEnd].Price = kIfinityPrice; + UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(0, lenTest2, state2, posStateNext); + COptimal &optimum = _optimum[offset]; + if (curAndLenPrice < optimum.Price) + { + optimum.Price = curAndLenPrice; + optimum.PosPrev = cur + lenTest + 1; + optimum.BackPrev = 0; + optimum.Prev1IsChar = true; + optimum.Prev2 = true; + optimum.PosPrev2 = cur; + optimum.BackPrev2 = curBack + kNumRepDistances; + } + } + } + offs += 2; + if (offs == numDistancePairs) + break; + curBack = matchDistances[offs + 1]; + if (curBack >= kNumFullDistances) + posSlot = GetPosSlot2(curBack); + } + } + } + } +} + +static inline bool ChangePair(UInt32 smallDist, UInt32 bigDist) +{ + return ((bigDist >> 7) > smallDist); +} + + +HRESULT CEncoder::ReadMatchDistances(UInt32 &lenRes, UInt32 &numDistancePairs) +{ + lenRes = 0; + RINOK(_matchFinder->GetMatches(_matchDistances)); + numDistancePairs = _matchDistances[0]; + if (numDistancePairs > 0) + { + lenRes = _matchDistances[1 + numDistancePairs - 2]; + if (lenRes == _numFastBytes) + lenRes += _matchFinder->GetMatchLen(lenRes - 1, _matchDistances[1 + numDistancePairs - 1], + kMatchMaxLen - lenRes); + } + _additionalOffset++; + return S_OK; +} + +HRESULT CEncoder::GetOptimumFast(UInt32 position, UInt32 &backRes, UInt32 &lenRes) +{ + UInt32 lenMain, numDistancePairs; + if (!_longestMatchWasFound) + { + RINOK(ReadMatchDistances(lenMain, numDistancePairs)); + } + else + { + lenMain = _longestMatchLength; + numDistancePairs = _numDistancePairs; + _longestMatchWasFound = false; + } + + const Byte *data = _matchFinder->GetPointerToCurrentPos() - 1; + UInt32 numAvailableBytes = _matchFinder->GetNumAvailableBytes() + 1; + if (numAvailableBytes > kMatchMaxLen) + numAvailableBytes = kMatchMaxLen; + if (numAvailableBytes < 2) + { + backRes = (UInt32)(-1); + lenRes = 1; + return S_OK; + } + + UInt32 repLens[kNumRepDistances]; + UInt32 repMaxIndex = 0; + + for(UInt32 i = 0; i < kNumRepDistances; i++) + { + UInt32 backOffset = _repDistances[i] + 1; + if (data[0] != data[(size_t)0 - backOffset] || data[1] != data[(size_t)1 - backOffset]) + { + repLens[i] = 0; + continue; + } + UInt32 len; + for (len = 2; len < numAvailableBytes && data[len] == data[(size_t)len - backOffset]; len++); + if(len >= _numFastBytes) + { + backRes = i; + lenRes = len; + return MovePos(lenRes - 1); + } + repLens[i] = len; + if (len > repLens[repMaxIndex]) + repMaxIndex = i; + } + UInt32 *matchDistances = _matchDistances + 1; + if(lenMain >= _numFastBytes) + { + backRes = matchDistances[numDistancePairs - 1] + kNumRepDistances; + lenRes = lenMain; + return MovePos(lenMain - 1); + } + + UInt32 backMain = 0; + if (lenMain >= 2) + { + backMain = matchDistances[numDistancePairs - 1]; + while (numDistancePairs > 2 && lenMain == matchDistances[numDistancePairs - 4] + 1) + { + if (!ChangePair(matchDistances[numDistancePairs - 3], backMain)) + break; + numDistancePairs -= 2; + lenMain = matchDistances[numDistancePairs - 2]; + backMain = matchDistances[numDistancePairs - 1]; + } + if (lenMain == 2 && backMain >= 0x80) + lenMain = 1; + } + + if (repLens[repMaxIndex] >= 2) + { + if (repLens[repMaxIndex] + 1 >= lenMain || + repLens[repMaxIndex] + 2 >= lenMain && (backMain > (1 << 9)) || + repLens[repMaxIndex] + 3 >= lenMain && (backMain > (1 << 15))) + { + backRes = repMaxIndex; + lenRes = repLens[repMaxIndex]; + return MovePos(lenRes - 1); + } + } + + if (lenMain >= 2 && numAvailableBytes > 2) + { + RINOK(ReadMatchDistances(_longestMatchLength, _numDistancePairs)); + if (_longestMatchLength >= 2) + { + UInt32 newDistance = matchDistances[_numDistancePairs - 1]; + if (_longestMatchLength >= lenMain && newDistance < backMain || + _longestMatchLength == lenMain + 1 && !ChangePair(backMain, newDistance) || + _longestMatchLength > lenMain + 1 || + _longestMatchLength + 1 >= lenMain && lenMain >= 3 && ChangePair(newDistance, backMain)) + { + _longestMatchWasFound = true; + backRes = UInt32(-1); + lenRes = 1; + return S_OK; + } + } + data++; + numAvailableBytes--; + for(UInt32 i = 0; i < kNumRepDistances; i++) + { + UInt32 backOffset = _repDistances[i] + 1; + if (data[1] != data[(size_t)1 - backOffset] || data[2] != data[(size_t)2 - backOffset]) + { + repLens[i] = 0; + continue; + } + UInt32 len; + for (len = 2; len < numAvailableBytes && data[len] == data[(size_t)len - backOffset]; len++); + if (len + 1 >= lenMain) + { + _longestMatchWasFound = true; + backRes = UInt32(-1); + lenRes = 1; + return S_OK; + } + } + backRes = backMain + kNumRepDistances; + lenRes = lenMain; + return MovePos(lenMain - 2); + } + backRes = UInt32(-1); + lenRes = 1; + return S_OK; +} + +HRESULT CEncoder::Flush(UInt32 nowPos) +{ + ReleaseMFStream(); + WriteEndMarker(nowPos & _posStateMask); + _rangeEncoder.FlushData(); + return _rangeEncoder.FlushStream(); +} + +void CEncoder::WriteEndMarker(UInt32 posState) +{ + // This function for writing End Mark for stream version of LZMA. + // In current version this feature is not used. + if (!_writeEndMark) + return; + + _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1); + _isRep[_state.Index].Encode(&_rangeEncoder, 0); + _state.UpdateMatch(); + UInt32 len = kMatchMinLen; // kMatchMaxLen; + _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode); + UInt32 posSlot = (1 << kNumPosSlotBits) - 1; + UInt32 lenToPosState = GetLenToPosState(len); + _posSlotEncoder[lenToPosState].Encode(&_rangeEncoder, posSlot); + UInt32 footerBits = 30; + UInt32 posReduced = (UInt32(1) << footerBits) - 1; + _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits); + _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask); +} + +HRESULT CEncoder::CodeReal(ISequentialInStream *inStream, + ISequentialOutStream *outStream, + const UInt64 *inSize, const UInt64 *outSize, + ICompressProgressInfo *progress) +{ + _needReleaseMFStream = false; + CCoderReleaser coderReleaser(this); + RINOK(SetStreams(inStream, outStream, inSize, outSize)); + while(true) + { + UInt64 processedInSize; + UInt64 processedOutSize; + Int32 finished; + RINOK(CodeOneBlock(&processedInSize, &processedOutSize, &finished)); + if (finished != 0) + return S_OK; + if (progress != 0) + { + RINOK(progress->SetRatioInfo(&processedInSize, &processedOutSize)); + } + } +} + +HRESULT CEncoder::SetStreams(ISequentialInStream *inStream, + ISequentialOutStream *outStream, + const UInt64 *inSize, const UInt64 *outSize) +{ + _inStream = inStream; + _finished = false; + RINOK(Create()); + RINOK(SetOutStream(outStream)); + RINOK(Init()); + + // CCoderReleaser releaser(this); + + /* + if (_matchFinder->GetNumAvailableBytes() == 0) + return Flush(); + */ + + if (!_fastMode) + { + FillDistancesPrices(); + FillAlignPrices(); + } + + _lenEncoder.SetTableSize(_numFastBytes + 1 - kMatchMinLen); + _lenEncoder.UpdateTables(1 << _posStateBits); + _repMatchLenEncoder.SetTableSize(_numFastBytes + 1 - kMatchMinLen); + _repMatchLenEncoder.UpdateTables(1 << _posStateBits); + + nowPos64 = 0; + return S_OK; +} + +HRESULT CEncoder::CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished) +{ + if (_inStream != 0) + { + RINOK(_matchFinder->SetStream(_inStream)); + RINOK(_matchFinder->Init()); + _needReleaseMFStream = true; + _inStream = 0; + } + + + *finished = 1; + if (_finished) + return S_OK; + _finished = true; + + if (nowPos64 == 0) + { + if (_matchFinder->GetNumAvailableBytes() == 0) + return Flush(UInt32(nowPos64)); + UInt32 len, numDistancePairs; + RINOK(ReadMatchDistances(len, numDistancePairs)); + UInt32 posState = UInt32(nowPos64) & _posStateMask; + _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0); + _state.UpdateChar(); + Byte curByte = _matchFinder->GetIndexByte(0 - _additionalOffset); + _literalEncoder.GetSubCoder(UInt32(nowPos64), _previousByte)->Encode(&_rangeEncoder, curByte); + _previousByte = curByte; + _additionalOffset--; + nowPos64++; + } + + UInt32 nowPos32 = (UInt32)nowPos64; + UInt32 progressPosValuePrev = nowPos32; + + if (_matchFinder->GetNumAvailableBytes() == 0) + return Flush(nowPos32); + + while(true) + { + #ifdef _NO_EXCEPTIONS + if (_rangeEncoder.Stream.ErrorCode != S_OK) + return _rangeEncoder.Stream.ErrorCode; + #endif + UInt32 pos, len; + HRESULT result; + if (_fastMode) + result = GetOptimumFast(nowPos32, pos, len); + else + result = GetOptimum(nowPos32, pos, len); + RINOK(result); + + UInt32 posState = nowPos32 & _posStateMask; + if(len == 1 && pos == 0xFFFFFFFF) + { + _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0); + Byte curByte = _matchFinder->GetIndexByte(0 - _additionalOffset); + CLiteralEncoder2 *subCoder = _literalEncoder.GetSubCoder(nowPos32, _previousByte); + if(_state.IsCharState()) + subCoder->Encode(&_rangeEncoder, curByte); + else + { + Byte matchByte = _matchFinder->GetIndexByte(0 - _repDistances[0] - 1 - _additionalOffset); + subCoder->EncodeMatched(&_rangeEncoder, matchByte, curByte); + } + _state.UpdateChar(); + _previousByte = curByte; + } + else + { + _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1); + if(pos < kNumRepDistances) + { + _isRep[_state.Index].Encode(&_rangeEncoder, 1); + if(pos == 0) + { + _isRepG0[_state.Index].Encode(&_rangeEncoder, 0); + _isRep0Long[_state.Index][posState].Encode(&_rangeEncoder, ((len == 1) ? 0 : 1)); + } + else + { + UInt32 distance = _repDistances[pos]; + _isRepG0[_state.Index].Encode(&_rangeEncoder, 1); + if (pos == 1) + _isRepG1[_state.Index].Encode(&_rangeEncoder, 0); + else + { + _isRepG1[_state.Index].Encode(&_rangeEncoder, 1); + _isRepG2[_state.Index].Encode(&_rangeEncoder, pos - 2); + if (pos == 3) + _repDistances[3] = _repDistances[2]; + _repDistances[2] = _repDistances[1]; + } + _repDistances[1] = _repDistances[0]; + _repDistances[0] = distance; + } + if (len == 1) + _state.UpdateShortRep(); + else + { + _repMatchLenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode); + _state.UpdateRep(); + } + } + else + { + _isRep[_state.Index].Encode(&_rangeEncoder, 0); + _state.UpdateMatch(); + _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode); + pos -= kNumRepDistances; + UInt32 posSlot = GetPosSlot(pos); + _posSlotEncoder[GetLenToPosState(len)].Encode(&_rangeEncoder, posSlot); + + if (posSlot >= kStartPosModelIndex) + { + UInt32 footerBits = ((posSlot >> 1) - 1); + UInt32 base = ((2 | (posSlot & 1)) << footerBits); + UInt32 posReduced = pos - base; + + if (posSlot < kEndPosModelIndex) + NRangeCoder::ReverseBitTreeEncode(_posEncoders + base - posSlot - 1, + &_rangeEncoder, footerBits, posReduced); + else + { + _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits); + _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask); + _alignPriceCount++; + } + } + _repDistances[3] = _repDistances[2]; + _repDistances[2] = _repDistances[1]; + _repDistances[1] = _repDistances[0]; + _repDistances[0] = pos; + _matchPriceCount++; + } + _previousByte = _matchFinder->GetIndexByte(len - 1 - _additionalOffset); + } + _additionalOffset -= len; + nowPos32 += len; + if (_additionalOffset == 0) + { + if (!_fastMode) + { + if (_matchPriceCount >= (1 << 7)) + FillDistancesPrices(); + if (_alignPriceCount >= kAlignTableSize) + FillAlignPrices(); + } + if (_matchFinder->GetNumAvailableBytes() == 0) + return Flush(nowPos32); + if (nowPos32 - progressPosValuePrev >= (1 << 14)) + { + nowPos64 += nowPos32 - progressPosValuePrev; + *inSize = nowPos64; + *outSize = _rangeEncoder.GetProcessedSize(); + _finished = false; + *finished = 0; + return S_OK; + } + } + } +} + +STDMETHODIMP CEncoder::Code(ISequentialInStream *inStream, + ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize, + ICompressProgressInfo *progress) +{ + #ifndef _NO_EXCEPTIONS + try + { + #endif + return CodeReal(inStream, outStream, inSize, outSize, progress); + #ifndef _NO_EXCEPTIONS + } + catch(const COutBufferException &e) { return e.ErrorCode; } + catch(...) { return E_FAIL; } + #endif +} + +void CEncoder::FillDistancesPrices() +{ + UInt32 tempPrices[kNumFullDistances]; + for (UInt32 i = kStartPosModelIndex; i < kNumFullDistances; i++) + { + UInt32 posSlot = GetPosSlot(i); + UInt32 footerBits = ((posSlot >> 1) - 1); + UInt32 base = ((2 | (posSlot & 1)) << footerBits); + tempPrices[i] = NRangeCoder::ReverseBitTreeGetPrice(_posEncoders + + base - posSlot - 1, footerBits, i - base); + } + + for (UInt32 lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++) + { + UInt32 posSlot; + NRangeCoder::CBitTreeEncoder &encoder = _posSlotEncoder[lenToPosState]; + UInt32 *posSlotPrices = _posSlotPrices[lenToPosState]; + for (posSlot = 0; posSlot < _distTableSize; posSlot++) + posSlotPrices[posSlot] = encoder.GetPrice(posSlot); + for (posSlot = kEndPosModelIndex; posSlot < _distTableSize; posSlot++) + posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << NRangeCoder::kNumBitPriceShiftBits); + + UInt32 *distancesPrices = _distancesPrices[lenToPosState]; + UInt32 i; + for (i = 0; i < kStartPosModelIndex; i++) + distancesPrices[i] = posSlotPrices[i]; + for (; i < kNumFullDistances; i++) + distancesPrices[i] = posSlotPrices[GetPosSlot(i)] + tempPrices[i]; + } + _matchPriceCount = 0; +} + +void CEncoder::FillAlignPrices() +{ + for (UInt32 i = 0; i < kAlignTableSize; i++) + _alignPrices[i] = _posAlignEncoder.ReverseGetPrice(i); + _alignPriceCount = 0; +} + +}} diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMAEncoder.h b/util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMAEncoder.h new file mode 100644 index 0000000000..f4c2c15131 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMAEncoder.h @@ -0,0 +1,411 @@ +// LZMA/Encoder.h + +#ifndef __LZMA_ENCODER_H +#define __LZMA_ENCODER_H + +#include "../../../Common/MyCom.h" +#include "../../../Common/Alloc.h" +#include "../../ICoder.h" +#include "../LZ/IMatchFinder.h" +#include "../RangeCoder/RangeCoderBitTree.h" + +#include "LZMA.h" + +namespace NCompress { +namespace NLZMA { + +typedef NRangeCoder::CBitEncoder CMyBitEncoder; + +class CBaseState +{ +protected: + CState _state; + Byte _previousByte; + UInt32 _repDistances[kNumRepDistances]; + void Init() + { + _state.Init(); + _previousByte = 0; + for(UInt32 i = 0 ; i < kNumRepDistances; i++) + _repDistances[i] = 0; + } +}; + +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[1 << 11]; +inline UInt32 GetPosSlot(UInt32 pos) +{ + if (pos < (1 << 11)) + return g_FastPos[pos]; + if (pos < (1 << 21)) + return g_FastPos[pos >> 10] + 20; + return g_FastPos[pos >> 20] + 40; +} + +inline UInt32 GetPosSlot2(UInt32 pos) +{ + if (pos < (1 << 17)) + return g_FastPos[pos >> 6] + 12; + if (pos < (1 << 27)) + return g_FastPos[pos >> 16] + 32; + return g_FastPos[pos >> 26] + 52; +} + +const UInt32 kIfinityPrice = 0xFFFFFFF; + +const UInt32 kNumOpts = 1 << 12; + + +class CLiteralEncoder2 +{ + CMyBitEncoder _encoders[0x300]; +public: + void Init() + { + for (int i = 0; i < 0x300; i++) + _encoders[i].Init(); + } + void Encode(NRangeCoder::CEncoder *rangeEncoder, Byte symbol); + void EncodeMatched(NRangeCoder::CEncoder *rangeEncoder, Byte matchByte, Byte symbol); + UInt32 GetPrice(bool matchMode, Byte matchByte, Byte symbol) const; +}; + +class CLiteralEncoder +{ + CLiteralEncoder2 *_coders; + int _numPrevBits; + int _numPosBits; + UInt32 _posMask; +public: + CLiteralEncoder(): _coders(0) {} + ~CLiteralEncoder() { Free(); } + void Free() + { + MyFree(_coders); + _coders = 0; + } + bool Create(int numPosBits, int numPrevBits) + { + if (_coders == 0 || (numPosBits + numPrevBits) != (_numPrevBits + _numPosBits)) + { + Free(); + UInt32 numStates = 1 << (numPosBits + numPrevBits); + _coders = (CLiteralEncoder2 *)MyAlloc(numStates * sizeof(CLiteralEncoder2)); + } + _numPosBits = numPosBits; + _posMask = (1 << numPosBits) - 1; + _numPrevBits = numPrevBits; + return (_coders != 0); + } + void Init() + { + UInt32 numStates = 1 << (_numPrevBits + _numPosBits); + for (UInt32 i = 0; i < numStates; i++) + _coders[i].Init(); + } + CLiteralEncoder2 *GetSubCoder(UInt32 pos, Byte prevByte) + { return &_coders[((pos & _posMask) << _numPrevBits) + (prevByte >> (8 - _numPrevBits))]; } +}; + +namespace NLength { + +class CEncoder +{ + CMyBitEncoder _choice; + CMyBitEncoder _choice2; + NRangeCoder::CBitTreeEncoder _lowCoder[kNumPosStatesEncodingMax]; + NRangeCoder::CBitTreeEncoder _midCoder[kNumPosStatesEncodingMax]; + NRangeCoder::CBitTreeEncoder _highCoder; +public: + void Init(UInt32 numPosStates); + void Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState); + void SetPrices(UInt32 posState, UInt32 numSymbols, UInt32 *prices) const; +}; + +const UInt32 kNumSpecSymbols = kNumLowSymbols + kNumMidSymbols; + +class CPriceTableEncoder: public CEncoder +{ + UInt32 _prices[kNumPosStatesEncodingMax][kNumSymbolsTotal]; + UInt32 _tableSize; + UInt32 _counters[kNumPosStatesEncodingMax]; +public: + void SetTableSize(UInt32 tableSize) { _tableSize = tableSize; } + UInt32 GetPrice(UInt32 symbol, UInt32 posState) const { return _prices[posState][symbol]; } + void UpdateTable(UInt32 posState) + { + SetPrices(posState, _tableSize, _prices[posState]); + _counters[posState] = _tableSize; + } + void UpdateTables(UInt32 numPosStates) + { + for (UInt32 posState = 0; posState < numPosStates; posState++) + UpdateTable(posState); + } + void Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState, bool updatePrice) + { + CEncoder::Encode(rangeEncoder, symbol, posState); + if (updatePrice) + if (--_counters[posState] == 0) + UpdateTable(posState); + } +}; + +} + +class CEncoder : + public ICompressCoder, + public ICompressSetOutStream, + public ICompressSetCoderProperties, + public ICompressWriteCoderProperties, + public CBaseState, + public CMyUnknownImp +{ + COptimal _optimum[kNumOpts]; + CMyComPtr _matchFinder; // test it + NRangeCoder::CEncoder _rangeEncoder; + + CMyBitEncoder _isMatch[kNumStates][NLength::kNumPosStatesEncodingMax]; + CMyBitEncoder _isRep[kNumStates]; + CMyBitEncoder _isRepG0[kNumStates]; + CMyBitEncoder _isRepG1[kNumStates]; + CMyBitEncoder _isRepG2[kNumStates]; + CMyBitEncoder _isRep0Long[kNumStates][NLength::kNumPosStatesEncodingMax]; + + NRangeCoder::CBitTreeEncoder _posSlotEncoder[kNumLenToPosStates]; + + CMyBitEncoder _posEncoders[kNumFullDistances - kEndPosModelIndex]; + NRangeCoder::CBitTreeEncoder _posAlignEncoder; + + NLength::CPriceTableEncoder _lenEncoder; + NLength::CPriceTableEncoder _repMatchLenEncoder; + + CLiteralEncoder _literalEncoder; + + UInt32 _matchDistances[kMatchMaxLen * 2 + 2 + 1]; + + bool _fastMode; + // bool _maxMode; + UInt32 _numFastBytes; + UInt32 _longestMatchLength; + UInt32 _numDistancePairs; + + UInt32 _additionalOffset; + + UInt32 _optimumEndIndex; + UInt32 _optimumCurrentIndex; + + bool _longestMatchWasFound; + + UInt32 _posSlotPrices[kNumLenToPosStates][kDistTableSizeMax]; + + UInt32 _distancesPrices[kNumLenToPosStates][kNumFullDistances]; + + UInt32 _alignPrices[kAlignTableSize]; + UInt32 _alignPriceCount; + + UInt32 _distTableSize; + + UInt32 _posStateBits; + UInt32 _posStateMask; + UInt32 _numLiteralPosStateBits; + UInt32 _numLiteralContextBits; + + UInt32 _dictionarySize; + + UInt32 _dictionarySizePrev; + UInt32 _numFastBytesPrev; + + UInt32 _matchPriceCount; + UInt64 nowPos64; + bool _finished; + ISequentialInStream *_inStream; + + UInt32 _matchFinderCycles; + int _matchFinderIndex; + #ifdef COMPRESS_MF_MT + bool _multiThread; + #endif + + bool _writeEndMark; + + bool _needReleaseMFStream; + + IMatchFinderSetNumPasses *setMfPasses; + + void ReleaseMatchFinder() + { + setMfPasses = 0; + _matchFinder.Release(); + } + + HRESULT ReadMatchDistances(UInt32 &len, UInt32 &numDistancePairs); + + HRESULT MovePos(UInt32 num); + UInt32 GetRepLen1Price(CState state, UInt32 posState) const + { + return _isRepG0[state.Index].GetPrice0() + + _isRep0Long[state.Index][posState].GetPrice0(); + } + + UInt32 GetPureRepPrice(UInt32 repIndex, CState state, UInt32 posState) const + { + UInt32 price; + if(repIndex == 0) + { + price = _isRepG0[state.Index].GetPrice0(); + price += _isRep0Long[state.Index][posState].GetPrice1(); + } + else + { + price = _isRepG0[state.Index].GetPrice1(); + if (repIndex == 1) + price += _isRepG1[state.Index].GetPrice0(); + else + { + price += _isRepG1[state.Index].GetPrice1(); + price += _isRepG2[state.Index].GetPrice(repIndex - 2); + } + } + return price; + } + UInt32 GetRepPrice(UInt32 repIndex, UInt32 len, CState state, UInt32 posState) const + { + return _repMatchLenEncoder.GetPrice(len - kMatchMinLen, posState) + + GetPureRepPrice(repIndex, state, posState); + } + /* + UInt32 GetPosLen2Price(UInt32 pos, UInt32 posState) const + { + if (pos >= kNumFullDistances) + return kIfinityPrice; + return _distancesPrices[0][pos] + _lenEncoder.GetPrice(0, posState); + } + UInt32 GetPosLen3Price(UInt32 pos, UInt32 len, UInt32 posState) const + { + UInt32 price; + UInt32 lenToPosState = GetLenToPosState(len); + if (pos < kNumFullDistances) + price = _distancesPrices[lenToPosState][pos]; + else + price = _posSlotPrices[lenToPosState][GetPosSlot2(pos)] + + _alignPrices[pos & kAlignMask]; + return price + _lenEncoder.GetPrice(len - kMatchMinLen, posState); + } + */ + UInt32 GetPosLenPrice(UInt32 pos, UInt32 len, UInt32 posState) const + { + UInt32 price; + UInt32 lenToPosState = GetLenToPosState(len); + if (pos < kNumFullDistances) + price = _distancesPrices[lenToPosState][pos]; + else + price = _posSlotPrices[lenToPosState][GetPosSlot2(pos)] + + _alignPrices[pos & kAlignMask]; + return price + _lenEncoder.GetPrice(len - kMatchMinLen, posState); + } + + UInt32 Backward(UInt32 &backRes, UInt32 cur); + HRESULT GetOptimum(UInt32 position, UInt32 &backRes, UInt32 &lenRes); + HRESULT GetOptimumFast(UInt32 position, UInt32 &backRes, UInt32 &lenRes); + + void FillDistancesPrices(); + void FillAlignPrices(); + + void ReleaseMFStream() + { + if (_matchFinder && _needReleaseMFStream) + { + _matchFinder->ReleaseStream(); + _needReleaseMFStream = false; + } + } + + void ReleaseStreams() + { + ReleaseMFStream(); + ReleaseOutStream(); + } + + HRESULT Flush(UInt32 nowPos); + class CCoderReleaser + { + CEncoder *_coder; + public: + CCoderReleaser(CEncoder *coder): _coder(coder) {} + ~CCoderReleaser() + { + _coder->ReleaseStreams(); + } + }; + friend class CCoderReleaser; + + void WriteEndMarker(UInt32 posState); + +public: + CEncoder(); + void SetWriteEndMarkerMode(bool writeEndMarker) + { _writeEndMark= writeEndMarker; } + + HRESULT Create(); + + MY_UNKNOWN_IMP3( + ICompressSetOutStream, + ICompressSetCoderProperties, + ICompressWriteCoderProperties + ) + + HRESULT Init(); + + // ICompressCoder interface + HRESULT SetStreams(ISequentialInStream *inStream, + ISequentialOutStream *outStream, + const UInt64 *inSize, const UInt64 *outSize); + HRESULT CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished); + + HRESULT CodeReal(ISequentialInStream *inStream, + ISequentialOutStream *outStream, + const UInt64 *inSize, const UInt64 *outSize, + ICompressProgressInfo *progress); + + // ICompressCoder interface + STDMETHOD(Code)(ISequentialInStream *inStream, + ISequentialOutStream *outStream, + const UInt64 *inSize, const UInt64 *outSize, + ICompressProgressInfo *progress); + + // ICompressSetCoderProperties2 + STDMETHOD(SetCoderProperties)(const PROPID *propIDs, + const PROPVARIANT *properties, UInt32 numProperties); + + // ICompressWriteCoderProperties + STDMETHOD(WriteCoderProperties)(ISequentialOutStream *outStream); + + STDMETHOD(SetOutStream)(ISequentialOutStream *outStream); + STDMETHOD(ReleaseOutStream)(); + + virtual ~CEncoder() {} +}; + +}} + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/LZMA/StdAfx.h b/util/cbfstool/lzma/C/7zip/Compress/LZMA/StdAfx.h new file mode 100644 index 0000000000..e7fb6986d2 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/LZMA/StdAfx.h @@ -0,0 +1,8 @@ +// StdAfx.h + +#ifndef __STDAFX_H +#define __STDAFX_H + +#include "../../../Common/MyWindows.h" + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoder.h b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoder.h new file mode 100644 index 0000000000..bbb2ba82d3 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoder.h @@ -0,0 +1,205 @@ +// Compress/RangeCoder/RangeCoder.h + +#ifndef __COMPRESS_RANGECODER_H +#define __COMPRESS_RANGECODER_H + +#include "../../Common/InBuffer.h" +#include "../../Common/OutBuffer.h" + +namespace NCompress { +namespace NRangeCoder { + +const int kNumTopBits = 24; +const UInt32 kTopValue = (1 << kNumTopBits); + +class CEncoder +{ + UInt32 _cacheSize; + Byte _cache; +public: + UInt64 Low; + UInt32 Range; + COutBuffer Stream; + bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); } + + void SetStream(ISequentialOutStream *stream) { Stream.SetStream(stream); } + void Init() + { + Stream.Init(); + Low = 0; + Range = 0xFFFFFFFF; + _cacheSize = 1; + _cache = 0; + } + + void FlushData() + { + // Low += 1; + for(int i = 0; i < 5; i++) + ShiftLow(); + } + + HRESULT FlushStream() { return Stream.Flush(); } + + void ReleaseStream() { Stream.ReleaseStream(); } + + void Encode(UInt32 start, UInt32 size, UInt32 total) + { + Low += start * (Range /= total); + Range *= size; + while (Range < kTopValue) + { + Range <<= 8; + ShiftLow(); + } + } + + void ShiftLow() + { + if ((UInt32)Low < (UInt32)0xFF000000 || (int)(Low >> 32) != 0) + { + Byte temp = _cache; + do + { + Stream.WriteByte((Byte)(temp + (Byte)(Low >> 32))); + temp = 0xFF; + } + while(--_cacheSize != 0); + _cache = (Byte)((UInt32)Low >> 24); + } + _cacheSize++; + Low = (UInt32)Low << 8; + } + + void EncodeDirectBits(UInt32 value, int numTotalBits) + { + for (int i = numTotalBits - 1; i >= 0; i--) + { + Range >>= 1; + if (((value >> i) & 1) == 1) + Low += Range; + if (Range < kTopValue) + { + Range <<= 8; + ShiftLow(); + } + } + } + + void EncodeBit(UInt32 size0, UInt32 numTotalBits, UInt32 symbol) + { + UInt32 newBound = (Range >> numTotalBits) * size0; + if (symbol == 0) + Range = newBound; + else + { + Low += newBound; + Range -= newBound; + } + while (Range < kTopValue) + { + Range <<= 8; + ShiftLow(); + } + } + + UInt64 GetProcessedSize() { return Stream.GetProcessedSize() + _cacheSize + 4; } +}; + +class CDecoder +{ +public: + CInBuffer Stream; + UInt32 Range; + UInt32 Code; + bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); } + + void Normalize() + { + while (Range < kTopValue) + { + Code = (Code << 8) | Stream.ReadByte(); + Range <<= 8; + } + } + + void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); } + void Init() + { + Stream.Init(); + Code = 0; + Range = 0xFFFFFFFF; + for(int i = 0; i < 5; i++) + Code = (Code << 8) | Stream.ReadByte(); + } + + void ReleaseStream() { Stream.ReleaseStream(); } + + UInt32 GetThreshold(UInt32 total) + { + return (Code) / ( Range /= total); + } + + void Decode(UInt32 start, UInt32 size) + { + Code -= start * Range; + Range *= size; + Normalize(); + } + + UInt32 DecodeDirectBits(int numTotalBits) + { + UInt32 range = Range; + UInt32 code = Code; + UInt32 result = 0; + for (int i = numTotalBits; i != 0; i--) + { + range >>= 1; + /* + result <<= 1; + if (code >= range) + { + code -= range; + result |= 1; + } + */ + UInt32 t = (code - range) >> 31; + code -= range & (t - 1); + result = (result << 1) | (1 - t); + + if (range < kTopValue) + { + code = (code << 8) | Stream.ReadByte(); + range <<= 8; + } + } + Range = range; + Code = code; + return result; + } + + UInt32 DecodeBit(UInt32 size0, UInt32 numTotalBits) + { + UInt32 newBound = (Range >> numTotalBits) * size0; + UInt32 symbol; + if (Code < newBound) + { + symbol = 0; + Range = newBound; + } + else + { + symbol = 1; + Code -= newBound; + Range -= newBound; + } + Normalize(); + return symbol; + } + + UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); } +}; + +}} + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.cpp b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.cpp new file mode 100644 index 0000000000..8e4c4d3a9e --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.cpp @@ -0,0 +1,80 @@ +// Compress/RangeCoder/RangeCoderBit.cpp + +#include "StdAfx.h" + +#include "RangeCoderBit.h" + +namespace NCompress { +namespace NRangeCoder { + +UInt32 CPriceTables::ProbPrices[kBitModelTotal >> kNumMoveReducingBits]; +static CPriceTables g_PriceTables; + +CPriceTables::CPriceTables() { Init(); } + +void CPriceTables::Init() +{ + const int kNumBits = (kNumBitModelTotalBits - kNumMoveReducingBits); + for(int i = kNumBits - 1; i >= 0; i--) + { + UInt32 start = 1 << (kNumBits - i - 1); + UInt32 end = 1 << (kNumBits - i); + for (UInt32 j = start; j < end; j++) + ProbPrices[j] = (i << kNumBitPriceShiftBits) + + (((end - j) << kNumBitPriceShiftBits) >> (kNumBits - i - 1)); + } + + /* + // simplest: bad solution + for(UInt32 i = 1; i < (kBitModelTotal >> kNumMoveReducingBits) - 1; i++) + ProbPrices[i] = kBitPrice; + */ + + /* + const double kDummyMultMid = (1.0 / kBitPrice) / 2; + const double kDummyMultMid = 0; + // float solution + double ln2 = log(double(2)); + double lnAll = log(double(kBitModelTotal >> kNumMoveReducingBits)); + for(UInt32 i = 1; i < (kBitModelTotal >> kNumMoveReducingBits) - 1; i++) + ProbPrices[i] = UInt32((fabs(lnAll - log(double(i))) / ln2 + kDummyMultMid) * kBitPrice); + */ + + /* + // experimental, slow, solution: + for(UInt32 i = 1; i < (kBitModelTotal >> kNumMoveReducingBits) - 1; i++) + { + const int kCyclesBits = 5; + const UInt32 kCycles = (1 << kCyclesBits); + + UInt32 range = UInt32(-1); + UInt32 bitCount = 0; + for (UInt32 j = 0; j < kCycles; j++) + { + range >>= (kNumBitModelTotalBits - kNumMoveReducingBits); + range *= i; + while(range < (1 << 31)) + { + range <<= 1; + bitCount++; + } + } + bitCount <<= kNumBitPriceShiftBits; + range -= (1 << 31); + for (int k = kNumBitPriceShiftBits - 1; k >= 0; k--) + { + range <<= 1; + if (range > (1 << 31)) + { + bitCount += (1 << k); + range -= (1 << 31); + } + } + ProbPrices[i] = (bitCount + // + (1 << (kCyclesBits - 1)) + ) >> kCyclesBits; + } + */ +} + +}} diff --git a/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.h b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.h new file mode 100644 index 0000000000..624f887c94 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.h @@ -0,0 +1,120 @@ +// Compress/RangeCoder/RangeCoderBit.h + +#ifndef __COMPRESS_RANGECODER_BIT_H +#define __COMPRESS_RANGECODER_BIT_H + +#include "RangeCoder.h" + +namespace NCompress { +namespace NRangeCoder { + +const int kNumBitModelTotalBits = 11; +const UInt32 kBitModelTotal = (1 << kNumBitModelTotalBits); + +const int kNumMoveReducingBits = 2; + +const int kNumBitPriceShiftBits = 6; +const UInt32 kBitPrice = 1 << kNumBitPriceShiftBits; + +class CPriceTables +{ +public: + static UInt32 ProbPrices[kBitModelTotal >> kNumMoveReducingBits]; + static void Init(); + CPriceTables(); +}; + +template +class CBitModel +{ +public: + UInt32 Prob; + void UpdateModel(UInt32 symbol) + { + /* + Prob -= (Prob + ((symbol - 1) & ((1 << numMoveBits) - 1))) >> numMoveBits; + Prob += (1 - symbol) << (kNumBitModelTotalBits - numMoveBits); + */ + if (symbol == 0) + Prob += (kBitModelTotal - Prob) >> numMoveBits; + else + Prob -= (Prob) >> numMoveBits; + } +public: + void Init() { Prob = kBitModelTotal / 2; } +}; + +template +class CBitEncoder: public CBitModel +{ +public: + void Encode(CEncoder *encoder, UInt32 symbol) + { + /* + encoder->EncodeBit(this->Prob, kNumBitModelTotalBits, symbol); + this->UpdateModel(symbol); + */ + UInt32 newBound = (encoder->Range >> kNumBitModelTotalBits) * this->Prob; + if (symbol == 0) + { + encoder->Range = newBound; + this->Prob += (kBitModelTotal - this->Prob) >> numMoveBits; + } + else + { + encoder->Low += newBound; + encoder->Range -= newBound; + this->Prob -= (this->Prob) >> numMoveBits; + } + if (encoder->Range < kTopValue) + { + encoder->Range <<= 8; + encoder->ShiftLow(); + } + } + UInt32 GetPrice(UInt32 symbol) const + { + return CPriceTables::ProbPrices[ + (((this->Prob - symbol) ^ ((-(int)symbol))) & (kBitModelTotal - 1)) >> kNumMoveReducingBits]; + } + UInt32 GetPrice0() const { return CPriceTables::ProbPrices[this->Prob >> kNumMoveReducingBits]; } + UInt32 GetPrice1() const { return CPriceTables::ProbPrices[(kBitModelTotal - this->Prob) >> kNumMoveReducingBits]; } +}; + + +template +class CBitDecoder: public CBitModel +{ +public: + UInt32 Decode(CDecoder *decoder) + { + UInt32 newBound = (decoder->Range >> kNumBitModelTotalBits) * this->Prob; + if (decoder->Code < newBound) + { + decoder->Range = newBound; + this->Prob += (kBitModelTotal - this->Prob) >> numMoveBits; + if (decoder->Range < kTopValue) + { + decoder->Code = (decoder->Code << 8) | decoder->Stream.ReadByte(); + decoder->Range <<= 8; + } + return 0; + } + else + { + decoder->Range -= newBound; + decoder->Code -= newBound; + this->Prob -= (this->Prob) >> numMoveBits; + if (decoder->Range < kTopValue) + { + decoder->Code = (decoder->Code << 8) | decoder->Stream.ReadByte(); + decoder->Range <<= 8; + } + return 1; + } + } +}; + +}} + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBitTree.h b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBitTree.h new file mode 100644 index 0000000000..4f0c78b49d --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderBitTree.h @@ -0,0 +1,161 @@ +// Compress/RangeCoder/RangeCoderBitTree.h + +#ifndef __COMPRESS_RANGECODER_BIT_TREE_H +#define __COMPRESS_RANGECODER_BIT_TREE_H + +#include "RangeCoderBit.h" +#include "RangeCoderOpt.h" + +namespace NCompress { +namespace NRangeCoder { + +template +class CBitTreeEncoder +{ + CBitEncoder Models[1 << NumBitLevels]; +public: + void Init() + { + for(UInt32 i = 1; i < (1 << NumBitLevels); i++) + Models[i].Init(); + } + void Encode(CEncoder *rangeEncoder, UInt32 symbol) + { + UInt32 modelIndex = 1; + for (int bitIndex = NumBitLevels; bitIndex != 0 ;) + { + bitIndex--; + UInt32 bit = (symbol >> bitIndex) & 1; + Models[modelIndex].Encode(rangeEncoder, bit); + modelIndex = (modelIndex << 1) | bit; + } + }; + void ReverseEncode(CEncoder *rangeEncoder, UInt32 symbol) + { + UInt32 modelIndex = 1; + for (int i = 0; i < NumBitLevels; i++) + { + UInt32 bit = symbol & 1; + Models[modelIndex].Encode(rangeEncoder, bit); + modelIndex = (modelIndex << 1) | bit; + symbol >>= 1; + } + } + UInt32 GetPrice(UInt32 symbol) const + { + symbol |= (1 << NumBitLevels); + UInt32 price = 0; + while (symbol != 1) + { + price += Models[symbol >> 1].GetPrice(symbol & 1); + symbol >>= 1; + } + return price; + } + UInt32 ReverseGetPrice(UInt32 symbol) const + { + UInt32 price = 0; + UInt32 modelIndex = 1; + for (int i = NumBitLevels; i != 0; i--) + { + UInt32 bit = symbol & 1; + symbol >>= 1; + price += Models[modelIndex].GetPrice(bit); + modelIndex = (modelIndex << 1) | bit; + } + return price; + } +}; + +template +class CBitTreeDecoder +{ + CBitDecoder Models[1 << NumBitLevels]; +public: + void Init() + { + for(UInt32 i = 1; i < (1 << NumBitLevels); i++) + Models[i].Init(); + } + UInt32 Decode(CDecoder *rangeDecoder) + { + UInt32 modelIndex = 1; + RC_INIT_VAR + for(int bitIndex = NumBitLevels; bitIndex != 0; bitIndex--) + { + // modelIndex = (modelIndex << 1) + Models[modelIndex].Decode(rangeDecoder); + RC_GETBIT(numMoveBits, Models[modelIndex].Prob, modelIndex) + } + RC_FLUSH_VAR + return modelIndex - (1 << NumBitLevels); + }; + UInt32 ReverseDecode(CDecoder *rangeDecoder) + { + UInt32 modelIndex = 1; + UInt32 symbol = 0; + RC_INIT_VAR + for(int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++) + { + // UInt32 bit = Models[modelIndex].Decode(rangeDecoder); + // modelIndex <<= 1; + // modelIndex += bit; + // symbol |= (bit << bitIndex); + RC_GETBIT2(numMoveBits, Models[modelIndex].Prob, modelIndex, ; , symbol |= (1 << bitIndex)) + } + RC_FLUSH_VAR + return symbol; + } +}; + +template +void ReverseBitTreeEncode(CBitEncoder *Models, + CEncoder *rangeEncoder, int NumBitLevels, UInt32 symbol) +{ + UInt32 modelIndex = 1; + for (int i = 0; i < NumBitLevels; i++) + { + UInt32 bit = symbol & 1; + Models[modelIndex].Encode(rangeEncoder, bit); + modelIndex = (modelIndex << 1) | bit; + symbol >>= 1; + } +} + +template +UInt32 ReverseBitTreeGetPrice(CBitEncoder *Models, + UInt32 NumBitLevels, UInt32 symbol) +{ + UInt32 price = 0; + UInt32 modelIndex = 1; + for (int i = NumBitLevels; i != 0; i--) + { + UInt32 bit = symbol & 1; + symbol >>= 1; + price += Models[modelIndex].GetPrice(bit); + modelIndex = (modelIndex << 1) | bit; + } + return price; +} + +template +UInt32 ReverseBitTreeDecode(CBitDecoder *Models, + CDecoder *rangeDecoder, int NumBitLevels) +{ + UInt32 modelIndex = 1; + UInt32 symbol = 0; + RC_INIT_VAR + for(int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++) + { + // UInt32 bit = Models[modelIndex].Decode(rangeDecoder); + // modelIndex <<= 1; + // modelIndex += bit; + // symbol |= (bit << bitIndex); + RC_GETBIT2(numMoveBits, Models[modelIndex].Prob, modelIndex, ; , symbol |= (1 << bitIndex)) + } + RC_FLUSH_VAR + return symbol; +} + +}} + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderOpt.h b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderOpt.h new file mode 100644 index 0000000000..668b9a5b0a --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/RangeCoderOpt.h @@ -0,0 +1,31 @@ +// Compress/RangeCoder/RangeCoderOpt.h + +#ifndef __COMPRESS_RANGECODER_OPT_H +#define __COMPRESS_RANGECODER_OPT_H + +#define RC_INIT_VAR \ + UInt32 range = rangeDecoder->Range; \ + UInt32 code = rangeDecoder->Code; + +#define RC_FLUSH_VAR \ + rangeDecoder->Range = range; \ + rangeDecoder->Code = code; + +#define RC_NORMALIZE \ + if (range < NCompress::NRangeCoder::kTopValue) \ + { code = (code << 8) | rangeDecoder->Stream.ReadByte(); range <<= 8; } + +#define RC_GETBIT2(numMoveBits, prob, mi, A0, A1) \ + { UInt32 bound = (range >> NCompress::NRangeCoder::kNumBitModelTotalBits) * prob; \ + if (code < bound) \ + { A0; range = bound; \ + prob += (NCompress::NRangeCoder::kBitModelTotal - prob) >> numMoveBits; \ + mi <<= 1; } \ + else \ + { A1; range -= bound; code -= bound; prob -= (prob) >> numMoveBits; \ + mi = (mi + mi) + 1; }} \ + RC_NORMALIZE + +#define RC_GETBIT(numMoveBits, prob, mi) RC_GETBIT2(numMoveBits, prob, mi, ; , ;) + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/StdAfx.h b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/StdAfx.h new file mode 100644 index 0000000000..b637fd4007 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Compress/RangeCoder/StdAfx.h @@ -0,0 +1,6 @@ +// StdAfx.h + +#ifndef __STDAFX_H +#define __STDAFX_H + +#endif diff --git a/util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.c b/util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.c new file mode 100644 index 0000000000..21bf40bde0 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.c @@ -0,0 +1,588 @@ +/* + LzmaDecode.c + LZMA Decoder (optimized for Speed version) + + LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10) + http://www.7-zip.org/ + + LZMA SDK is licensed under two licenses: + 1) GNU Lesser General Public License (GNU LGPL) + 2) Common Public License (CPL) + It means that you can select one of these two licenses and + follow rules of that license. + + SPECIAL EXCEPTION: + Igor Pavlov, as the author of this Code, expressly permits you to + statically or dynamically link your Code (or bind by name) to the + interfaces of this file without subjecting your linked Code to the + terms of the CPL or GNU LGPL. Any modifications or additions + to this file, however, are subject to the LGPL or CPL terms. +*/ + +#include "LzmaDecode.h" + +#ifndef Byte +#define Byte unsigned char +#endif + +#define kNumTopBits 24 +#define kTopValue ((UInt32)1 << kNumTopBits) + +#define kNumBitModelTotalBits 11 +#define kBitModelTotal (1 << kNumBitModelTotalBits) +#define kNumMoveBits 5 + +#define RC_READ_BYTE (*Buffer++) + +#define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \ + { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }} + +#ifdef _LZMA_IN_CB + +#define RC_TEST { if (Buffer == BufferLim) \ + { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \ + BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }} + +#define RC_INIT Buffer = BufferLim = 0; RC_INIT2 + +#else + +#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; } + +#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2 + +#endif + +#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; } + +#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound) +#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits; +#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits; + +#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \ + { UpdateBit0(p); mi <<= 1; A0; } else \ + { UpdateBit1(p); mi = (mi + mi) + 1; A1; } + +#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;) + +#define RangeDecoderBitTreeDecode(probs, numLevels, res) \ + { int i = numLevels; res = 1; \ + do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \ + res -= (1 << numLevels); } + + +#define kNumPosBitsMax 4 +#define kNumPosStatesMax (1 << kNumPosBitsMax) + +#define kLenNumLowBits 3 +#define kLenNumLowSymbols (1 << kLenNumLowBits) +#define kLenNumMidBits 3 +#define kLenNumMidSymbols (1 << kLenNumMidBits) +#define kLenNumHighBits 8 +#define kLenNumHighSymbols (1 << kLenNumHighBits) + +#define LenChoice 0 +#define LenChoice2 (LenChoice + 1) +#define LenLow (LenChoice2 + 1) +#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) +#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) +#define kNumLenProbs (LenHigh + kLenNumHighSymbols) + + +#define kNumStates 12 +#define kNumLitStates 7 + +#define kStartPosModelIndex 4 +#define kEndPosModelIndex 14 +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) + +#define kNumPosSlotBits 6 +#define kNumLenToPosStates 4 + +#define kNumAlignBits 4 +#define kAlignTableSize (1 << kNumAlignBits) + +#define kMatchMinLen 2 + +#define IsMatch 0 +#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) +#define IsRepG0 (IsRep + kNumStates) +#define IsRepG1 (IsRepG0 + kNumStates) +#define IsRepG2 (IsRepG1 + kNumStates) +#define IsRep0Long (IsRepG2 + kNumStates) +#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) +#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) +#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) +#define LenCoder (Align + kAlignTableSize) +#define RepLenCoder (LenCoder + kNumLenProbs) +#define Literal (RepLenCoder + kNumLenProbs) + +#if Literal != LZMA_BASE_SIZE +StopCompilingDueBUG +#endif + +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size) +{ + unsigned char prop0; + if (size < LZMA_PROPERTIES_SIZE) + return LZMA_RESULT_DATA_ERROR; + prop0 = propsData[0]; + if (prop0 >= (9 * 5 * 5)) + return LZMA_RESULT_DATA_ERROR; + { + for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5)); + for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9); + propsRes->lc = prop0; + /* + unsigned char remainder = (unsigned char)(prop0 / 9); + propsRes->lc = prop0 % 9; + propsRes->pb = remainder / 5; + propsRes->lp = remainder % 5; + */ + } + + #ifdef _LZMA_OUT_READ + { + int i; + propsRes->DictionarySize = 0; + for (i = 0; i < 4; i++) + propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8); + if (propsRes->DictionarySize == 0) + propsRes->DictionarySize = 1; + } + #endif + return LZMA_RESULT_OK; +} + +#define kLzmaStreamWasFinishedId (-1) + +int LzmaDecode(CLzmaDecoderState *vs, + #ifdef _LZMA_IN_CB + ILzmaInCallback *InCallback, + #else + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, + #endif + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed) +{ + CProb *p = vs->Probs; + SizeT nowPos = 0; + Byte previousByte = 0; + UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1; + UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1; + int lc = vs->Properties.lc; + + #ifdef _LZMA_OUT_READ + + UInt32 Range = vs->Range; + UInt32 Code = vs->Code; + #ifdef _LZMA_IN_CB + const Byte *Buffer = vs->Buffer; + const Byte *BufferLim = vs->BufferLim; + #else + const Byte *Buffer = inStream; + const Byte *BufferLim = inStream + inSize; + #endif + int state = vs->State; + UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3]; + int len = vs->RemainLen; + UInt32 globalPos = vs->GlobalPos; + UInt32 distanceLimit = vs->DistanceLimit; + + Byte *dictionary = vs->Dictionary; + UInt32 dictionarySize = vs->Properties.DictionarySize; + UInt32 dictionaryPos = vs->DictionaryPos; + + Byte tempDictionary[4]; + + #ifndef _LZMA_IN_CB + *inSizeProcessed = 0; + #endif + *outSizeProcessed = 0; + if (len == kLzmaStreamWasFinishedId) + return LZMA_RESULT_OK; + + if (dictionarySize == 0) + { + dictionary = tempDictionary; + dictionarySize = 1; + tempDictionary[0] = vs->TempDictionary[0]; + } + + if (len == kLzmaNeedInitId) + { + { + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); + UInt32 i; + for (i = 0; i < numProbs; i++) + p[i] = kBitModelTotal >> 1; + rep0 = rep1 = rep2 = rep3 = 1; + state = 0; + globalPos = 0; + distanceLimit = 0; + dictionaryPos = 0; + dictionary[dictionarySize - 1] = 0; + #ifdef _LZMA_IN_CB + RC_INIT; + #else + RC_INIT(inStream, inSize); + #endif + } + len = 0; + } + while(len != 0 && nowPos < outSize) + { + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos]; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + len--; + } + if (dictionaryPos == 0) + previousByte = dictionary[dictionarySize - 1]; + else + previousByte = dictionary[dictionaryPos - 1]; + + #else /* if !_LZMA_OUT_READ */ + + int state = 0; + UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1; + int len = 0; + const Byte *Buffer; + const Byte *BufferLim; + UInt32 Range; + UInt32 Code; + + #ifndef _LZMA_IN_CB + *inSizeProcessed = 0; + #endif + *outSizeProcessed = 0; + + { + UInt32 i; + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); + for (i = 0; i < numProbs; i++) + p[i] = kBitModelTotal >> 1; + } + + #ifdef _LZMA_IN_CB + RC_INIT; + #else + RC_INIT(inStream, inSize); + #endif + + #endif /* _LZMA_OUT_READ */ + + while(nowPos < outSize) + { + CProb *prob; + UInt32 bound; + int posState = (int)( + (nowPos + #ifdef _LZMA_OUT_READ + + globalPos + #endif + ) + & posStateMask); + + prob = p + IsMatch + (state << kNumPosBitsMax) + posState; + IfBit0(prob) + { + int symbol = 1; + UpdateBit0(prob) + prob = p + Literal + (LZMA_LIT_SIZE * + ((( + (nowPos + #ifdef _LZMA_OUT_READ + + globalPos + #endif + ) + & literalPosMask) << lc) + (previousByte >> (8 - lc)))); + + if (state >= kNumLitStates) + { + int matchByte; + #ifdef _LZMA_OUT_READ + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + matchByte = dictionary[pos]; + #else + matchByte = outStream[nowPos - rep0]; + #endif + do + { + int bit; + CProb *probLit; + matchByte <<= 1; + bit = (matchByte & 0x100); + probLit = prob + 0x100 + bit + symbol; + RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break) + } + while (symbol < 0x100); + } + while (symbol < 0x100) + { + CProb *probLit = prob + symbol; + RC_GET_BIT(probLit, symbol) + } + previousByte = (Byte)symbol; + + outStream[nowPos++] = previousByte; + #ifdef _LZMA_OUT_READ + if (distanceLimit < dictionarySize) + distanceLimit++; + + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + #endif + if (state < 4) state = 0; + else if (state < 10) state -= 3; + else state -= 6; + } + else + { + UpdateBit1(prob); + prob = p + IsRep + state; + IfBit0(prob) + { + UpdateBit0(prob); + rep3 = rep2; + rep2 = rep1; + rep1 = rep0; + state = state < kNumLitStates ? 0 : 3; + prob = p + LenCoder; + } + else + { + UpdateBit1(prob); + prob = p + IsRepG0 + state; + IfBit0(prob) + { + UpdateBit0(prob); + prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState; + IfBit0(prob) + { + #ifdef _LZMA_OUT_READ + UInt32 pos; + #endif + UpdateBit0(prob); + + #ifdef _LZMA_OUT_READ + if (distanceLimit == 0) + #else + if (nowPos == 0) + #endif + return LZMA_RESULT_DATA_ERROR; + + state = state < kNumLitStates ? 9 : 11; + #ifdef _LZMA_OUT_READ + pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + previousByte = dictionary[pos]; + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + #else + previousByte = outStream[nowPos - rep0]; + #endif + outStream[nowPos++] = previousByte; + #ifdef _LZMA_OUT_READ + if (distanceLimit < dictionarySize) + distanceLimit++; + #endif + + continue; + } + else + { + UpdateBit1(prob); + } + } + else + { + UInt32 distance; + UpdateBit1(prob); + prob = p + IsRepG1 + state; + IfBit0(prob) + { + UpdateBit0(prob); + distance = rep1; + } + else + { + UpdateBit1(prob); + prob = p + IsRepG2 + state; + IfBit0(prob) + { + UpdateBit0(prob); + distance = rep2; + } + else + { + UpdateBit1(prob); + distance = rep3; + rep3 = rep2; + } + rep2 = rep1; + } + rep1 = rep0; + rep0 = distance; + } + state = state < kNumLitStates ? 8 : 11; + prob = p + RepLenCoder; + } + { + int numBits, offset; + CProb *probLen = prob + LenChoice; + IfBit0(probLen) + { + UpdateBit0(probLen); + probLen = prob + LenLow + (posState << kLenNumLowBits); + offset = 0; + numBits = kLenNumLowBits; + } + else + { + UpdateBit1(probLen); + probLen = prob + LenChoice2; + IfBit0(probLen) + { + UpdateBit0(probLen); + probLen = prob + LenMid + (posState << kLenNumMidBits); + offset = kLenNumLowSymbols; + numBits = kLenNumMidBits; + } + else + { + UpdateBit1(probLen); + probLen = prob + LenHigh; + offset = kLenNumLowSymbols + kLenNumMidSymbols; + numBits = kLenNumHighBits; + } + } + RangeDecoderBitTreeDecode(probLen, numBits, len); + len += offset; + } + + if (state < 4) + { + int posSlot; + state += kNumLitStates; + prob = p + PosSlot + + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << + kNumPosSlotBits); + RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot); + if (posSlot >= kStartPosModelIndex) + { + int numDirectBits = ((posSlot >> 1) - 1); + rep0 = (2 | ((UInt32)posSlot & 1)); + if (posSlot < kEndPosModelIndex) + { + rep0 <<= numDirectBits; + prob = p + SpecPos + rep0 - posSlot - 1; + } + else + { + numDirectBits -= kNumAlignBits; + do + { + RC_NORMALIZE + Range >>= 1; + rep0 <<= 1; + if (Code >= Range) + { + Code -= Range; + rep0 |= 1; + } + } + while (--numDirectBits != 0); + prob = p + Align; + rep0 <<= kNumAlignBits; + numDirectBits = kNumAlignBits; + } + { + int i = 1; + int mi = 1; + do + { + CProb *prob3 = prob + mi; + RC_GET_BIT2(prob3, mi, ; , rep0 |= i); + i <<= 1; + } + while(--numDirectBits != 0); + } + } + else + rep0 = posSlot; + if (++rep0 == (UInt32)(0)) + { + /* it's for stream version */ + len = kLzmaStreamWasFinishedId; + break; + } + } + + len += kMatchMinLen; + #ifdef _LZMA_OUT_READ + if (rep0 > distanceLimit) + #else + if (rep0 > nowPos) + #endif + return LZMA_RESULT_DATA_ERROR; + + #ifdef _LZMA_OUT_READ + if (dictionarySize - distanceLimit > (UInt32)len) + distanceLimit += len; + else + distanceLimit = dictionarySize; + #endif + + do + { + #ifdef _LZMA_OUT_READ + UInt32 pos = dictionaryPos - rep0; + if (pos >= dictionarySize) + pos += dictionarySize; + previousByte = dictionary[pos]; + dictionary[dictionaryPos] = previousByte; + if (++dictionaryPos == dictionarySize) + dictionaryPos = 0; + #else + previousByte = outStream[nowPos - rep0]; + #endif + len--; + outStream[nowPos++] = previousByte; + } + while(len != 0 && nowPos < outSize); + } + } + RC_NORMALIZE; + + #ifdef _LZMA_OUT_READ + vs->Range = Range; + vs->Code = Code; + vs->DictionaryPos = dictionaryPos; + vs->GlobalPos = globalPos + (UInt32)nowPos; + vs->DistanceLimit = distanceLimit; + vs->Reps[0] = rep0; + vs->Reps[1] = rep1; + vs->Reps[2] = rep2; + vs->Reps[3] = rep3; + vs->State = state; + vs->RemainLen = len; + vs->TempDictionary[0] = tempDictionary[0]; + #endif + + #ifdef _LZMA_IN_CB + vs->Buffer = Buffer; + vs->BufferLim = BufferLim; + #else + *inSizeProcessed = (SizeT)(Buffer - inStream); + #endif + *outSizeProcessed = nowPos; + return LZMA_RESULT_OK; +} diff --git a/util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.h b/util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.h new file mode 100644 index 0000000000..213062af12 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/Decompress/LzmaDecode.h @@ -0,0 +1,131 @@ +/* + LzmaDecode.h + LZMA Decoder interface + + LZMA SDK 4.21 Copyright (c) 1999-2005 Igor Pavlov (2005-06-08) + http://www.7-zip.org/ + + LZMA SDK is licensed under two licenses: + 1) GNU Lesser General Public License (GNU LGPL) + 2) Common Public License (CPL) + It means that you can select one of these two licenses and + follow rules of that license. + + SPECIAL EXCEPTION: + Igor Pavlov, as the author of this code, expressly permits you to + statically or dynamically link your code (or bind by name) to the + interfaces of this file without subjecting your linked code to the + terms of the CPL or GNU LGPL. Any modifications or additions + to this file, however, are subject to the LGPL or CPL terms. +*/ + +#ifndef __LZMADECODE_H +#define __LZMADECODE_H + +/* #define _LZMA_IN_CB */ +/* Use callback for input data */ + +/* #define _LZMA_OUT_READ */ +/* Use read function for output data */ + +/* #define _LZMA_PROB32 */ +/* It can increase speed on some 32-bit CPUs, + but memory usage will be doubled in that case */ + +/* #define _LZMA_LOC_OPT */ +/* Enable local speed optimizations inside code */ + +/* #define _LZMA_SYSTEM_SIZE_T */ +/* Use system's size_t. You can use it to enable 64-bit sizes supporting*/ + +#ifndef UInt32 +#ifdef _LZMA_UINT32_IS_ULONG +#define UInt32 unsigned long +#else +#define UInt32 unsigned int +#endif +#endif + +#ifndef SizeT +#ifdef _LZMA_SYSTEM_SIZE_T +#include +#define SizeT size_t +#else +#define SizeT UInt32 +#endif +#endif + +#ifdef _LZMA_PROB32 +#define CProb UInt32 +#else +#define CProb unsigned short +#endif + +#define LZMA_RESULT_OK 0 +#define LZMA_RESULT_DATA_ERROR 1 + +#ifdef _LZMA_IN_CB +typedef struct _ILzmaInCallback +{ + int (*Read)(void *object, const unsigned char **buffer, SizeT *bufferSize); +} ILzmaInCallback; +#endif + +#define LZMA_BASE_SIZE 1846 +#define LZMA_LIT_SIZE 768 + +#define LZMA_PROPERTIES_SIZE 5 + +typedef struct _CLzmaProperties +{ + int lc; + int lp; + int pb; + #ifdef _LZMA_OUT_READ + UInt32 DictionarySize; + #endif +}CLzmaProperties; + +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size); + +#define LzmaGetNumProbs(Properties) (LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((Properties)->lc + (Properties)->lp))) + +#define kLzmaNeedInitId (-2) + +typedef struct _CLzmaDecoderState +{ + CLzmaProperties Properties; + CProb *Probs; + + #ifdef _LZMA_IN_CB + const unsigned char *Buffer; + const unsigned char *BufferLim; + #endif + + #ifdef _LZMA_OUT_READ + unsigned char *Dictionary; + UInt32 Range; + UInt32 Code; + UInt32 DictionaryPos; + UInt32 GlobalPos; + UInt32 DistanceLimit; + UInt32 Reps[4]; + int State; + int RemainLen; + unsigned char TempDictionary[4]; + #endif +} CLzmaDecoderState; + +#ifdef _LZMA_OUT_READ +#define LzmaDecoderInit(vs) { (vs)->RemainLen = kLzmaNeedInitId; } +#endif + +int LzmaDecode(CLzmaDecoderState *vs, + #ifdef _LZMA_IN_CB + ILzmaInCallback *inCallback, + #else + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, + #endif + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed); + +#endif diff --git a/util/cbfstool/lzma/C/7zip/ICoder.h b/util/cbfstool/lzma/C/7zip/ICoder.h new file mode 100644 index 0000000000..d84575dc45 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/ICoder.h @@ -0,0 +1,163 @@ +// ICoder.h + +#ifndef __ICODER_H +#define __ICODER_H + +#include "IStream.h" + +// "23170F69-40C1-278A-0000-000400xx0000" +#define CODER_INTERFACE(i, x) \ +DEFINE_GUID(IID_ ## i, \ +0x23170F69, 0x40C1, 0x278A, 0x00, 0x00, 0x00, 0x04, 0x00, x, 0x00, 0x00); \ +struct i: public IUnknown + +CODER_INTERFACE(ICompressProgressInfo, 0x04) +{ + STDMETHOD(SetRatioInfo)(const UInt64 *inSize, const UInt64 *outSize) PURE; +}; + +CODER_INTERFACE(ICompressCoder, 0x05) +{ + STDMETHOD(Code)(ISequentialInStream *inStream, + ISequentialOutStream *outStream, + const UInt64 *inSize, + const UInt64 *outSize, + ICompressProgressInfo *progress) PURE; +}; + +CODER_INTERFACE(ICompressCoder2, 0x18) +{ + STDMETHOD(Code)(ISequentialInStream **inStreams, + const UInt64 **inSizes, + UInt32 numInStreams, + ISequentialOutStream **outStreams, + const UInt64 **outSizes, + UInt32 numOutStreams, + ICompressProgressInfo *progress) PURE; +}; + +namespace NCoderPropID +{ + enum EEnum + { + kDictionarySize = 0x400, + kUsedMemorySize, + kOrder, + kPosStateBits = 0x440, + kLitContextBits, + kLitPosBits, + kNumFastBytes = 0x450, + kMatchFinder, + kMatchFinderCycles, + kNumPasses = 0x460, + kAlgorithm = 0x470, + kMultiThread = 0x480, + kNumThreads, + kEndMarker = 0x490 + }; +} + +CODER_INTERFACE(ICompressSetCoderProperties, 0x20) +{ + STDMETHOD(SetCoderProperties)(const PROPID *propIDs, + const PROPVARIANT *properties, UInt32 numProperties) PURE; +}; + +/* +CODER_INTERFACE(ICompressSetCoderProperties, 0x21) +{ + STDMETHOD(SetDecoderProperties)(ISequentialInStream *inStream) PURE; +}; +*/ + +CODER_INTERFACE(ICompressSetDecoderProperties2, 0x22) +{ + STDMETHOD(SetDecoderProperties2)(const Byte *data, UInt32 size) PURE; +}; + +CODER_INTERFACE(ICompressWriteCoderProperties, 0x23) +{ + STDMETHOD(WriteCoderProperties)(ISequentialOutStream *outStreams) PURE; +}; + +CODER_INTERFACE(ICompressGetInStreamProcessedSize, 0x24) +{ + STDMETHOD(GetInStreamProcessedSize)(UInt64 *value) PURE; +}; + +CODER_INTERFACE(ICompressSetCoderMt, 0x25) +{ + STDMETHOD(SetNumberOfThreads)(UInt32 numThreads) PURE; +}; + +CODER_INTERFACE(ICompressGetSubStreamSize, 0x30) +{ + STDMETHOD(GetSubStreamSize)(UInt64 subStream, UInt64 *value) PURE; +}; + +CODER_INTERFACE(ICompressSetInStream, 0x31) +{ + STDMETHOD(SetInStream)(ISequentialInStream *inStream) PURE; + STDMETHOD(ReleaseInStream)() PURE; +}; + +CODER_INTERFACE(ICompressSetOutStream, 0x32) +{ + STDMETHOD(SetOutStream)(ISequentialOutStream *outStream) PURE; + STDMETHOD(ReleaseOutStream)() PURE; +}; + +CODER_INTERFACE(ICompressSetInStreamSize, 0x33) +{ + STDMETHOD(SetInStreamSize)(const UInt64 *inSize) PURE; +}; + +CODER_INTERFACE(ICompressSetOutStreamSize, 0x34) +{ + STDMETHOD(SetOutStreamSize)(const UInt64 *outSize) PURE; +}; + +CODER_INTERFACE(ICompressFilter, 0x40) +{ + STDMETHOD(Init)() PURE; + STDMETHOD_(UInt32, Filter)(Byte *data, UInt32 size) PURE; + // Filter return outSize (UInt32) + // if (outSize <= size): Filter have converted outSize bytes + // if (outSize > size): Filter have not converted anything. + // and it needs at least outSize bytes to convert one block + // (it's for crypto block algorithms). +}; + +CODER_INTERFACE(ICryptoProperties, 0x80) +{ + STDMETHOD(SetKey)(const Byte *data, UInt32 size) PURE; + STDMETHOD(SetInitVector)(const Byte *data, UInt32 size) PURE; +}; + +CODER_INTERFACE(ICryptoSetPassword, 0x90) +{ + STDMETHOD(CryptoSetPassword)(const Byte *data, UInt32 size) PURE; +}; + +CODER_INTERFACE(ICryptoSetCRC, 0xA0) +{ + STDMETHOD(CryptoSetCRC)(UInt32 crc) PURE; +}; + +////////////////////// +// It's for DLL file +namespace NMethodPropID +{ + enum EEnum + { + kID, + kName, + kDecoder, + kEncoder, + kInStreams, + kOutStreams, + kDescription + }; +} + +#endif diff --git a/util/cbfstool/lzma/C/7zip/IStream.h b/util/cbfstool/lzma/C/7zip/IStream.h new file mode 100644 index 0000000000..bba21a3158 --- /dev/null +++ b/util/cbfstool/lzma/C/7zip/IStream.h @@ -0,0 +1,62 @@ +// IStream.h + +#ifndef __ISTREAM_H +#define __ISTREAM_H + +#include "../Common/MyUnknown.h" +#include "../Common/Types.h" + +// "23170F69-40C1-278A-0000-000300xx0000" + +#define STREAM_INTERFACE_SUB(i, b, x) \ +DEFINE_GUID(IID_ ## i, \ +0x23170F69, 0x40C1, 0x278A, 0x00, 0x00, 0x00, 0x03, 0x00, x, 0x00, 0x00); \ +struct i: public b + +#define STREAM_INTERFACE(i, x) STREAM_INTERFACE_SUB(i, IUnknown, x) + +STREAM_INTERFACE(ISequentialInStream, 0x01) +{ + STDMETHOD(Read)(void *data, UInt32 size, UInt32 *processedSize) PURE; + /* + Out: if size != 0, return_value = S_OK and (*processedSize == 0), + then there are no more bytes in stream. + if (size > 0) && there are bytes in stream, + this function must read at least 1 byte. + This function is allowed to read less than number of remaining bytes in stream. + You must call Read function in loop, if you need exact amount of data + */ +}; + +STREAM_INTERFACE(ISequentialOutStream, 0x02) +{ + STDMETHOD(Write)(const void *data, UInt32 size, UInt32 *processedSize) PURE; + /* + if (size > 0) this function must write at least 1 byte. + This function is allowed to write less than "size". + You must call Write function in loop, if you need to write exact amount of data + */ +}; + +STREAM_INTERFACE_SUB(IInStream, ISequentialInStream, 0x03) +{ + STDMETHOD(Seek)(Int64 offset, UInt32 seekOrigin, UInt64 *newPosition) PURE; +}; + +STREAM_INTERFACE_SUB(IOutStream, ISequentialOutStream, 0x04) +{ + STDMETHOD(Seek)(Int64 offset, UInt32 seekOrigin, UInt64 *newPosition) PURE; + STDMETHOD(SetSize)(Int64 newSize) PURE; +}; + +STREAM_INTERFACE(IStreamGetSize, 0x06) +{ + STDMETHOD(GetSize)(UInt64 *size) PURE; +}; + +STREAM_INTERFACE(IOutStreamFlush, 0x07) +{ + STDMETHOD(Flush)() PURE; +}; + +#endif diff --git a/util/cbfstool/lzma/C/Common/Alloc.cpp b/util/cbfstool/lzma/C/Common/Alloc.cpp new file mode 100644 index 0000000000..e2b8c3d289 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/Alloc.cpp @@ -0,0 +1,118 @@ +// Common/Alloc.cpp + +#include "StdAfx.h" + +#ifdef _WIN32 +#include "MyWindows.h" +#else +#include +#endif + +#include "Alloc.h" + +/* #define _SZ_ALLOC_DEBUG */ +/* use _SZ_ALLOC_DEBUG to debug alloc/free operations */ +#ifdef _SZ_ALLOC_DEBUG +#include +int g_allocCount = 0; +int g_allocCountMid = 0; +int g_allocCountBig = 0; +#endif + +void *MyAlloc(size_t size) throw() +{ + if (size == 0) + return 0; + #ifdef _SZ_ALLOC_DEBUG + fprintf(stderr, "\nAlloc %10d bytes; count = %10d", size, g_allocCount++); + #endif + return ::malloc(size); +} + +void MyFree(void *address) throw() +{ + #ifdef _SZ_ALLOC_DEBUG + if (address != 0) + fprintf(stderr, "\nFree; count = %10d", --g_allocCount); + #endif + + ::free(address); +} + +#ifdef _WIN32 + +void *MidAlloc(size_t size) throw() +{ + if (size == 0) + return 0; + #ifdef _SZ_ALLOC_DEBUG + fprintf(stderr, "\nAlloc_Mid %10d bytes; count = %10d", size, g_allocCountMid++); + #endif + return ::VirtualAlloc(0, size, MEM_COMMIT, PAGE_READWRITE); +} + +void MidFree(void *address) throw() +{ + #ifdef _SZ_ALLOC_DEBUG + if (address != 0) + fprintf(stderr, "\nFree_Mid; count = %10d", --g_allocCountMid); + #endif + if (address == 0) + return; + ::VirtualFree(address, 0, MEM_RELEASE); +} + +static SIZE_T g_LargePageSize = + #ifdef _WIN64 + (1 << 21); + #else + (1 << 22); + #endif + +typedef SIZE_T (WINAPI *GetLargePageMinimumP)(); + +bool SetLargePageSize() +{ + GetLargePageMinimumP largePageMinimum = (GetLargePageMinimumP) + ::GetProcAddress(::GetModuleHandle(TEXT("kernel32.dll")), "GetLargePageMinimum"); + if (largePageMinimum == 0) + return false; + SIZE_T size = largePageMinimum(); + if (size == 0 || (size & (size - 1)) != 0) + return false; + g_LargePageSize = size; + return true; +} + + +void *BigAlloc(size_t size) throw() +{ + if (size == 0) + return 0; + #ifdef _SZ_ALLOC_DEBUG + fprintf(stderr, "\nAlloc_Big %10d bytes; count = %10d", size, g_allocCountBig++); + #endif + + if (size >= (1 << 18)) + { + void *res = ::VirtualAlloc(0, (size + g_LargePageSize - 1) & (~(g_LargePageSize - 1)), + MEM_COMMIT | MEM_LARGE_PAGES, PAGE_READWRITE); + if (res != 0) + return res; + } + return ::VirtualAlloc(0, size, MEM_COMMIT, PAGE_READWRITE); +} + +void BigFree(void *address) throw() +{ + #ifdef _SZ_ALLOC_DEBUG + if (address != 0) + fprintf(stderr, "\nFree_Big; count = %10d", --g_allocCountBig); + #endif + + if (address == 0) + return; + ::VirtualFree(address, 0, MEM_RELEASE); +} + +#endif diff --git a/util/cbfstool/lzma/C/Common/Alloc.h b/util/cbfstool/lzma/C/Common/Alloc.h new file mode 100644 index 0000000000..d444f63193 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/Alloc.h @@ -0,0 +1,29 @@ +// Common/Alloc.h + +#ifndef __COMMON_ALLOC_H +#define __COMMON_ALLOC_H + +#include + +void *MyAlloc(size_t size) throw(); +void MyFree(void *address) throw(); + +#ifdef _WIN32 + +bool SetLargePageSize(); + +void *MidAlloc(size_t size) throw(); +void MidFree(void *address) throw(); +void *BigAlloc(size_t size) throw(); +void BigFree(void *address) throw(); + +#else + +#define MidAlloc(size) MyAlloc(size) +#define MidFree(address) MyFree(address) +#define BigAlloc(size) MyAlloc(size) +#define BigFree(address) MyFree(address) + +#endif + +#endif diff --git a/util/cbfstool/lzma/C/Common/CRC.cpp b/util/cbfstool/lzma/C/Common/CRC.cpp new file mode 100644 index 0000000000..35e1a18751 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/CRC.cpp @@ -0,0 +1,61 @@ +// Common/CRC.cpp + +#include "StdAfx.h" + +#include "CRC.h" + +static const UInt32 kCRCPoly = 0xEDB88320; + +UInt32 CCRC::Table[256]; + +void CCRC::InitTable() +{ + for (UInt32 i = 0; i < 256; i++) + { + UInt32 r = i; + for (int j = 0; j < 8; j++) + if (r & 1) + r = (r >> 1) ^ kCRCPoly; + else + r >>= 1; + CCRC::Table[i] = r; + } +} + +class CCRCTableInit +{ +public: + CCRCTableInit() { CCRC::InitTable(); } +} g_CRCTableInit; + +void CCRC::UpdateByte(Byte b) +{ + _value = Table[((Byte)(_value)) ^ b] ^ (_value >> 8); +} + +void CCRC::UpdateUInt16(UInt16 v) +{ + UpdateByte(Byte(v)); + UpdateByte(Byte(v >> 8)); +} + +void CCRC::UpdateUInt32(UInt32 v) +{ + for (int i = 0; i < 4; i++) + UpdateByte((Byte)(v >> (8 * i))); +} + +void CCRC::UpdateUInt64(UInt64 v) +{ + for (int i = 0; i < 8; i++) + UpdateByte((Byte)(v >> (8 * i))); +} + +void CCRC::Update(const void *data, size_t size) +{ + UInt32 v = _value; + const Byte *p = (const Byte *)data; + for (; size > 0 ; size--, p++) + v = Table[((Byte)(v)) ^ *p] ^ (v >> 8); + _value = v; +} diff --git a/util/cbfstool/lzma/C/Common/CRC.h b/util/cbfstool/lzma/C/Common/CRC.h new file mode 100644 index 0000000000..6b4f1b796b --- /dev/null +++ b/util/cbfstool/lzma/C/Common/CRC.h @@ -0,0 +1,36 @@ +// Common/CRC.h + +#ifndef __COMMON_CRC_H +#define __COMMON_CRC_H + +#include +#include "Types.h" + +class CCRC +{ + UInt32 _value; +public: + static UInt32 Table[256]; + static void InitTable(); + + CCRC(): _value(0xFFFFFFFF){}; + void Init() { _value = 0xFFFFFFFF; } + void UpdateByte(Byte v); + void UpdateUInt16(UInt16 v); + void UpdateUInt32(UInt32 v); + void UpdateUInt64(UInt64 v); + void Update(const void *data, size_t size); + UInt32 GetDigest() const { return _value ^ 0xFFFFFFFF; } + static UInt32 CalculateDigest(const void *data, size_t size) + { + CCRC crc; + crc.Update(data, size); + return crc.GetDigest(); + } + static bool VerifyDigest(UInt32 digest, const void *data, size_t size) + { + return (CalculateDigest(data, size) == digest); + } +}; + +#endif diff --git a/util/cbfstool/lzma/C/Common/Defs.h b/util/cbfstool/lzma/C/Common/Defs.h new file mode 100644 index 0000000000..dad3ae8f11 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/Defs.h @@ -0,0 +1,20 @@ +// Common/Defs.h + +#ifndef __COMMON_DEFS_H +#define __COMMON_DEFS_H + +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; } + +template inline int MyCompare(T a, T b) + { return a < b ? -1 : (a == b ? 0 : 1); } + +inline int BoolToInt(bool value) + { return (value ? 1: 0); } + +inline bool IntToBool(int value) + { return (value != 0); } + +#endif diff --git a/util/cbfstool/lzma/C/Common/MyCom.h b/util/cbfstool/lzma/C/Common/MyCom.h new file mode 100644 index 0000000000..e903493013 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/MyCom.h @@ -0,0 +1,203 @@ +// MyCom.h + +#ifndef __MYCOM_H +#define __MYCOM_H + +#include "MyWindows.h" + +#define RINOK(x) { HRESULT __result_ = (x); if(__result_ != S_OK) return __result_; } + +template +class CMyComPtr +{ + T* _p; +public: + // typedef T _PtrClass; + CMyComPtr() { _p = NULL;} + CMyComPtr(T* p) {if ((_p = p) != NULL) p->AddRef(); } + CMyComPtr(const CMyComPtr& lp) + { + if ((_p = lp._p) != NULL) + _p->AddRef(); + } + ~CMyComPtr() { if (_p) _p->Release(); } + void Release() { if (_p) { _p->Release(); _p = NULL; } } + operator T*() const { return (T*)_p; } + // T& operator*() const { return *_p; } + T** operator&() { return &_p; } + T* operator->() const { return _p; } + T* operator=(T* p) + { + if (p != 0) + p->AddRef(); + if (_p) + _p->Release(); + _p = p; + return p; + } + T* operator=(const CMyComPtr& lp) { return (*this = lp._p); } + bool operator!() const { return (_p == NULL); } + // bool operator==(T* pT) const { return _p == pT; } + // Compare two objects for equivalence + void Attach(T* p2) + { + Release(); + _p = p2; + } + T* Detach() + { + T* pt = _p; + _p = NULL; + return pt; + } + #ifdef _WIN32 + HRESULT CoCreateInstance(REFCLSID rclsid, REFIID iid, LPUNKNOWN pUnkOuter = NULL, DWORD dwClsContext = CLSCTX_ALL) + { + return ::CoCreateInstance(rclsid, pUnkOuter, dwClsContext, iid, (void**)&_p); + } + #endif + /* + HRESULT CoCreateInstance(LPCOLESTR szProgID, LPUNKNOWN pUnkOuter = NULL, DWORD dwClsContext = CLSCTX_ALL) + { + CLSID clsid; + HRESULT hr = CLSIDFromProgID(szProgID, &clsid); + ATLASSERT(_p == NULL); + if (SUCCEEDED(hr)) + hr = ::CoCreateInstance(clsid, pUnkOuter, dwClsContext, __uuidof(T), (void**)&_p); + return hr; + } + */ + template + HRESULT QueryInterface(REFGUID iid, Q** pp) const + { + return _p->QueryInterface(iid, (void**)pp); + } +}; + +////////////////////////////////////////////////////////// + +class CMyComBSTR +{ +public: + BSTR m_str; + CMyComBSTR() { m_str = NULL; } + CMyComBSTR(LPCOLESTR pSrc) { m_str = ::SysAllocString(pSrc); } + // CMyComBSTR(int nSize) { m_str = ::SysAllocStringLen(NULL, nSize); } + // CMyComBSTR(int nSize, LPCOLESTR sz) { m_str = ::SysAllocStringLen(sz, nSize); } + CMyComBSTR(const CMyComBSTR& src) { m_str = src.MyCopy(); } + /* + CMyComBSTR(REFGUID src) + { + LPOLESTR szGuid; + StringFromCLSID(src, &szGuid); + m_str = ::SysAllocString(szGuid); + CoTaskMemFree(szGuid); + } + */ + ~CMyComBSTR() { ::SysFreeString(m_str); } + CMyComBSTR& operator=(const CMyComBSTR& src) + { + if (m_str != src.m_str) + { + if (m_str) + ::SysFreeString(m_str); + m_str = src.MyCopy(); + } + return *this; + } + CMyComBSTR& operator=(LPCOLESTR pSrc) + { + ::SysFreeString(m_str); + m_str = ::SysAllocString(pSrc); + return *this; + } + unsigned int Length() const { return ::SysStringLen(m_str); } + operator BSTR() const { return m_str; } + BSTR* operator&() { return &m_str; } + BSTR MyCopy() const + { + int byteLen = ::SysStringByteLen(m_str); + BSTR res = ::SysAllocStringByteLen(NULL, byteLen); + memmove(res, m_str, byteLen); + return res; + } + void Attach(BSTR src) { m_str = src; } + BSTR Detach() + { + BSTR s = m_str; + m_str = NULL; + return s; + } + void Empty() + { + ::SysFreeString(m_str); + m_str = NULL; + } + bool operator!() const { return (m_str == NULL); } +}; + + +////////////////////////////////////////////////////////// + +class CMyUnknownImp +{ +public: + ULONG __m_RefCount; + CMyUnknownImp(): __m_RefCount(0) {} +}; + +#define MY_QUERYINTERFACE_BEGIN STDMETHOD(QueryInterface) \ + (REFGUID iid, void **outObject) { + +#define MY_QUERYINTERFACE_ENTRY(i) if (iid == IID_ ## i) \ + { *outObject = (void *)(i *)this; AddRef(); return S_OK; } + +#define MY_QUERYINTERFACE_END return E_NOINTERFACE; } + +#define MY_ADDREF_RELEASE \ +STDMETHOD_(ULONG, AddRef)() { return ++__m_RefCount; } \ +STDMETHOD_(ULONG, Release)() { if (--__m_RefCount != 0) \ + return __m_RefCount; delete this; return 0; } + +#define MY_UNKNOWN_IMP_SPEC(i) \ + MY_QUERYINTERFACE_BEGIN \ + i \ + MY_QUERYINTERFACE_END \ + MY_ADDREF_RELEASE + + +#define MY_UNKNOWN_IMP STDMETHOD(QueryInterface)(REFGUID, void **) { \ + MY_QUERYINTERFACE_END \ + MY_ADDREF_RELEASE + +#define MY_UNKNOWN_IMP1(i) MY_UNKNOWN_IMP_SPEC( \ + MY_QUERYINTERFACE_ENTRY(i) \ + ) + +#define MY_UNKNOWN_IMP2(i1, i2) MY_UNKNOWN_IMP_SPEC( \ + MY_QUERYINTERFACE_ENTRY(i1) \ + MY_QUERYINTERFACE_ENTRY(i2) \ + ) + +#define MY_UNKNOWN_IMP3(i1, i2, i3) MY_UNKNOWN_IMP_SPEC( \ + MY_QUERYINTERFACE_ENTRY(i1) \ + MY_QUERYINTERFACE_ENTRY(i2) \ + MY_QUERYINTERFACE_ENTRY(i3) \ + ) + +#define MY_UNKNOWN_IMP4(i1, i2, i3, i4) MY_UNKNOWN_IMP_SPEC( \ + MY_QUERYINTERFACE_ENTRY(i1) \ + MY_QUERYINTERFACE_ENTRY(i2) \ + MY_QUERYINTERFACE_ENTRY(i3) \ + MY_QUERYINTERFACE_ENTRY(i4) \ + ) + +#define MY_UNKNOWN_IMP5(i1, i2, i3, i4, i5) MY_UNKNOWN_IMP_SPEC( \ + MY_QUERYINTERFACE_ENTRY(i1) \ + MY_QUERYINTERFACE_ENTRY(i2) \ + MY_QUERYINTERFACE_ENTRY(i3) \ + MY_QUERYINTERFACE_ENTRY(i4) \ + MY_QUERYINTERFACE_ENTRY(i5) \ + ) + +#endif diff --git a/util/cbfstool/lzma/C/Common/MyGuidDef.h b/util/cbfstool/lzma/C/Common/MyGuidDef.h new file mode 100644 index 0000000000..a7f8118ec9 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/MyGuidDef.h @@ -0,0 +1,54 @@ +// Common/MyGuidDef.h + +#ifndef GUID_DEFINED +#define GUID_DEFINED + +#include "Types.h" + +typedef struct { + UInt32 Data1; + UInt16 Data2; + UInt16 Data3; + unsigned char Data4[8]; +} GUID; + +#ifdef __cplusplus +#define REFGUID const GUID & +#else +#define REFGUID const GUID * +#endif + +#define REFCLSID REFGUID +#define REFIID REFGUID + +#ifdef __cplusplus +inline bool operator==(REFGUID g1, REFGUID g2) +{ + for (int i = 0; i < (int)sizeof(g1); i++) + if (((const unsigned char *)&g1)[i] != ((const unsigned char *)&g2)[i]) + return false; + return true; +} +inline bool operator!=(REFGUID g1, REFGUID g2) { return !(g1 == g2); } +#endif + +#ifdef __cplusplus + #define MY_EXTERN_C extern "C" +#else + #define MY_EXTERN_C extern +#endif + +#endif // GUID_DEFINED + + +#ifdef DEFINE_GUID +#undef DEFINE_GUID +#endif + +#ifdef INITGUID + #define DEFINE_GUID(name, l, w1, w2, b1, b2, b3, b4, b5, b6, b7, b8) \ + MY_EXTERN_C const GUID name = { l, w1, w2, { b1, b2, b3, b4, b5, b6, b7, b8 } } +#else + #define DEFINE_GUID(name, l, w1, w2, b1, b2, b3, b4, b5, b6, b7, b8) \ + MY_EXTERN_C const GUID name +#endif diff --git a/util/cbfstool/lzma/C/Common/MyInitGuid.h b/util/cbfstool/lzma/C/Common/MyInitGuid.h new file mode 100644 index 0000000000..5bdfeed564 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/MyInitGuid.h @@ -0,0 +1,13 @@ +// Common/MyInitGuid.h + +#ifndef __COMMON_MYINITGUID_H +#define __COMMON_MYINITGUID_H + +#ifdef _WIN32 +#include +#else +#define INITGUID +#include "MyGuidDef.h" +#endif + +#endif diff --git a/util/cbfstool/lzma/C/Common/MyUnknown.h b/util/cbfstool/lzma/C/Common/MyUnknown.h new file mode 100644 index 0000000000..d28d854256 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/MyUnknown.h @@ -0,0 +1,24 @@ +// MyUnknown.h + +#ifndef __MYUNKNOWN_H +#define __MYUNKNOWN_H + +#ifdef _WIN32 + +#ifdef _WIN32_WCE +#if (_WIN32_WCE > 300) +#include +#else +#define MIDL_INTERFACE(x) struct +#endif +#else +#include +#endif + +#include + +#else +#include "MyWindows.h" +#endif + +#endif diff --git a/util/cbfstool/lzma/C/Common/MyWindows.h b/util/cbfstool/lzma/C/Common/MyWindows.h new file mode 100644 index 0000000000..0212fa77a3 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/MyWindows.h @@ -0,0 +1,201 @@ +// MyWindows.h + +#ifndef __MYWINDOWS_H +#define __MYWINDOWS_H + +#ifdef _WIN32 + +#include + +#define CHAR_PATH_SEPARATOR '\\' +#define WCHAR_PATH_SEPARATOR L'\\' +#define STRING_PATH_SEPARATOR "\\" +#define WSTRING_PATH_SEPARATOR L"\\" + +#else + +#define CHAR_PATH_SEPARATOR '/' +#define WCHAR_PATH_SEPARATOR L'/' +#define STRING_PATH_SEPARATOR "/" +#define WSTRING_PATH_SEPARATOR L"/" + +#include // for wchar_t +#include + +#include "MyGuidDef.h" + +typedef char CHAR; +typedef unsigned char UCHAR; + +#undef BYTE +typedef unsigned char BYTE; + +typedef short SHORT; +typedef unsigned short USHORT; + +#undef WORD +typedef unsigned short WORD; +typedef short VARIANT_BOOL; + +typedef int INT; +typedef Int32 INT32; +typedef unsigned int UINT; +typedef UInt32 UINT32; +typedef INT32 LONG; // LONG, ULONG and DWORD must be 32-bit +typedef UINT32 ULONG; + +#undef DWORD +typedef UINT32 DWORD; + +typedef Int64 LONGLONG; +typedef UInt64 ULONGLONG; + +typedef struct LARGE_INTEGER { LONGLONG QuadPart; }LARGE_INTEGER; +typedef struct _ULARGE_INTEGER { ULONGLONG QuadPart;} ULARGE_INTEGER; + +typedef const CHAR *LPCSTR; +typedef CHAR TCHAR; +typedef const TCHAR *LPCTSTR; +typedef wchar_t WCHAR; +typedef WCHAR OLECHAR; +typedef const WCHAR *LPCWSTR; +typedef OLECHAR *BSTR; +typedef const OLECHAR *LPCOLESTR; +typedef OLECHAR *LPOLESTR; + +typedef struct _FILETIME +{ + DWORD dwLowDateTime; + DWORD dwHighDateTime; +}FILETIME; + +#define HRESULT LONG +#define FAILED(Status) ((HRESULT)(Status)<0) +typedef ULONG PROPID; +typedef LONG SCODE; + +#define S_OK ((HRESULT)0x00000000L) +#define S_FALSE ((HRESULT)0x00000001L) +#define E_NOTIMPL ((HRESULT)0x80004001L) +#define E_NOINTERFACE ((HRESULT)0x80004002L) +#define E_ABORT ((HRESULT)0x80004004L) +#define E_FAIL ((HRESULT)0x80004005L) +#define STG_E_INVALIDFUNCTION ((HRESULT)0x80030001L) +#define E_OUTOFMEMORY ((HRESULT)0x8007000EL) +#define E_INVALIDARG ((HRESULT)0x80070057L) + +#ifdef _MSC_VER +#define STDMETHODCALLTYPE __stdcall +#else +#define STDMETHODCALLTYPE +#endif + +#define STDMETHOD_(t, f) virtual t STDMETHODCALLTYPE f +#define STDMETHOD(f) STDMETHOD_(HRESULT, f) +#define STDMETHODIMP_(type) type STDMETHODCALLTYPE +#define STDMETHODIMP STDMETHODIMP_(HRESULT) + +#define PURE = 0 + +#define MIDL_INTERFACE(x) struct + +struct IUnknown +{ + virtual ~IUnknown() {} + STDMETHOD(QueryInterface) (REFIID iid, void **outObject) PURE; + STDMETHOD_(ULONG, AddRef)() PURE; + STDMETHOD_(ULONG, Release)() PURE; +}; + +typedef IUnknown *LPUNKNOWN; + +#define VARIANT_TRUE ((VARIANT_BOOL)-1) +#define VARIANT_FALSE ((VARIANT_BOOL)0) + +enum VARENUM +{ + VT_EMPTY = 0, + VT_NULL = 1, + VT_I2 = 2, + VT_I4 = 3, + VT_R4 = 4, + VT_R8 = 5, + VT_CY = 6, + VT_DATE = 7, + VT_BSTR = 8, + VT_DISPATCH = 9, + VT_ERROR = 10, + VT_BOOL = 11, + VT_VARIANT = 12, + VT_UNKNOWN = 13, + VT_DECIMAL = 14, + VT_I1 = 16, + VT_UI1 = 17, + VT_UI2 = 18, + VT_UI4 = 19, + VT_I8 = 20, + VT_UI8 = 21, + VT_INT = 22, + VT_UINT = 23, + VT_VOID = 24, + VT_HRESULT = 25, + VT_FILETIME = 64 +}; + +typedef unsigned short VARTYPE; +typedef WORD PROPVAR_PAD1; +typedef WORD PROPVAR_PAD2; +typedef WORD PROPVAR_PAD3; + +typedef struct tagPROPVARIANT +{ + VARTYPE vt; + PROPVAR_PAD1 wReserved1; + PROPVAR_PAD2 wReserved2; + PROPVAR_PAD3 wReserved3; + union + { + CHAR cVal; + UCHAR bVal; + SHORT iVal; + USHORT uiVal; + LONG lVal; + ULONG ulVal; + INT intVal; + UINT uintVal; + LARGE_INTEGER hVal; + ULARGE_INTEGER uhVal; + VARIANT_BOOL boolVal; + SCODE scode; + FILETIME filetime; + BSTR bstrVal; + }; +} PROPVARIANT; + +typedef PROPVARIANT tagVARIANT; +typedef tagVARIANT VARIANT; +typedef VARIANT VARIANTARG; + +MY_EXTERN_C BSTR SysAllocStringByteLen(LPCSTR psz, UINT len); +MY_EXTERN_C BSTR SysAllocString(const OLECHAR *sz); +MY_EXTERN_C void SysFreeString(BSTR bstr); +MY_EXTERN_C UINT SysStringByteLen(BSTR bstr); +MY_EXTERN_C UINT SysStringLen(BSTR bstr); + +MY_EXTERN_C DWORD GetLastError(); +MY_EXTERN_C HRESULT VariantClear(VARIANTARG *prop); +MY_EXTERN_C HRESULT VariantCopy(VARIANTARG *dest, VARIANTARG *src); +MY_EXTERN_C LONG CompareFileTime(const FILETIME* ft1, const FILETIME* ft2); + +#define CP_ACP 0 +#define CP_OEMCP 1 + +typedef enum tagSTREAM_SEEK +{ + STREAM_SEEK_SET = 0, + STREAM_SEEK_CUR = 1, + STREAM_SEEK_END = 2 +} STREAM_SEEK; + +#endif +#endif diff --git a/util/cbfstool/lzma/C/Common/NewHandler.h b/util/cbfstool/lzma/C/Common/NewHandler.h new file mode 100644 index 0000000000..0619fc69e5 --- /dev/null +++ b/util/cbfstool/lzma/C/Common/NewHandler.h @@ -0,0 +1,16 @@ +// Common/NewHandler.h + +#ifndef __COMMON_NEWHANDLER_H +#define __COMMON_NEWHANDLER_H + +class CNewException {}; + +#ifdef _WIN32 +void +#ifdef _MSC_VER +__cdecl +#endif +operator delete(void *p) throw(); +#endif + +#endif diff --git a/util/cbfstool/lzma/C/Common/StdAfx.h b/util/cbfstool/lzma/C/Common/StdAfx.h new file mode 100644 index 0000000000..681ee9356e --- /dev/null +++ b/util/cbfstool/lzma/C/Common/StdAfx.h @@ -0,0 +1,9 @@ +// StdAfx.h + +#ifndef __STDAFX_H +#define __STDAFX_H + +// #include "MyWindows.h" +#include "NewHandler.h" + +#endif diff --git a/util/cbfstool/lzma/C/Common/Types.h b/util/cbfstool/lzma/C/Common/Types.h new file mode 100644 index 0000000000..0bf66e086b --- /dev/null +++ b/util/cbfstool/lzma/C/Common/Types.h @@ -0,0 +1,19 @@ +// Common/Types.h + +#ifndef __COMMON_TYPES_H +#define __COMMON_TYPES_H + +typedef unsigned char Byte; +typedef short Int16; +typedef unsigned short UInt16; +typedef int Int32; +typedef unsigned int UInt32; +#ifdef _MSC_VER +typedef __int64 Int64; +typedef unsigned __int64 UInt64; +#else +typedef long long int Int64; +typedef unsigned long long int UInt64; +#endif + +#endif diff --git a/util/cbfstool/lzma/C/LGPL.txt b/util/cbfstool/lzma/C/LGPL.txt new file mode 100644 index 0000000000..4c3890127d --- /dev/null +++ b/util/cbfstool/lzma/C/LGPL.txt @@ -0,0 +1,504 @@ + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it becomes +a de-facto standard. To achieve this, non-free programs must be +allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Libraries + + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). + + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. + + + Copyright (C) + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Also add information on how to contact you by electronic and paper mail. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the + library `Frob' (a library for tweaking knobs) written by James Random Hacker. + + , 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! + + diff --git a/util/cbfstool/lzma/C/ORIGIN b/util/cbfstool/lzma/C/ORIGIN new file mode 100644 index 0000000000..d1fbb7706d --- /dev/null +++ b/util/cbfstool/lzma/C/ORIGIN @@ -0,0 +1,3 @@ +The contents of this directory are extracted from +the official LZMA SDK, version lzma442.tar.bz2 , +for the use in mkcromfs. diff --git a/util/cbfstool/lzma/Makefile b/util/cbfstool/lzma/Makefile new file mode 100644 index 0000000000..9ac4ca2ff6 --- /dev/null +++ b/util/cbfstool/lzma/Makefile @@ -0,0 +1,50 @@ +## +## This file is part of the coreboot project. +## +## Copyright (C) 2007 coresystems GmbH +## +## This program is free software; you can redistribute it and/or modify +## it under the terms of the GNU General Public License as published by +## the Free Software Foundation; either version 2 of the License, or +## (at your option) any later version. +## +## This program is distributed in the hope that it will be useful, +## but WITHOUT ANY WARRANTY; without even the implied warranty of +## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +## GNU General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with this program; if not, write to the Free Software +## Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA +## + +LZMA_OBJ := lzma/LZMAEncoder.o lzma/LZInWindow.o +LZMA_OBJ += lzma/RangeCoderBit.o lzma/StreamUtils.o +LZMA_OBJ += lzma/OutBuffer.o lzma/Alloc.o +LZMA_OBJ += lzma/CRC.o +LZMA_OBJ += lzma/lzma-compress.o + +$(tobj)/lzma/lzma-compress.o: $(tsrc)/lzma/minilzma.cc + $(CXX) $(CFLAGS) -o $@ -c -DCOMPACT $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Compress/LZMA/%.cpp + $(CXX) $(CFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Compress/LZ/%.cpp + $(CXX) $(CFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Compress/RangeCoder/%.cpp + $(CXX) $(CFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Decompress/%.cpp + $(CXX) $(CFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Common/%.cpp + $(CXX) $(CFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/Common/%.cpp + $(CXX) $(CFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/%.cc + $(CXX) $(CFLAGS) -o $@ -c $< + diff --git a/util/cbfstool/lzma/Makefile.inc b/util/cbfstool/lzma/Makefile.inc new file mode 100644 index 0000000000..0dcec63e5f --- /dev/null +++ b/util/cbfstool/lzma/Makefile.inc @@ -0,0 +1,60 @@ +## +## This file is part of the coreboot project. +## +## Copyright (C) 2007 coresystems GmbH +## +## This program is free software; you can redistribute it and/or modify +## it under the terms of the GNU General Public License as published by +## the Free Software Foundation; either version 2 of the License, or +## (at your option) any later version. +## +## This program is distributed in the hope that it will be useful, +## but WITHOUT ANY WARRANTY; without even the implied warranty of +## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +## GNU General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with this program; if not, write to the Free Software +## Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA +## + +LZMA_OBJ := lzma/LZMAEncoder.o lzma/LZInWindow.o +LZMA_OBJ += lzma/RangeCoderBit.o lzma/StreamUtils.o +LZMA_OBJ += lzma/OutBuffer.o lzma/Alloc.o +LZMA_OBJ += lzma/CRC.o +LZMA_OBJ += lzma/lzma-compress.o + +ifdef POST_EVALUATION +$(tobj)/lzma/lzma-compress.o: $(tsrc)/lzma/minilzma.cc + printf " HOSTCXX $(subst $(obj)/,,$(@))\n" + $(HOSTCXX) $(HOSTCXXFLAGS) -o $@ -c -DCOMPACT $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Compress/LZMA/%.cpp + printf " HOSTCXX $(subst $(obj)/,,$(@))\n" + $(HOSTCXX) $(HOSTCXXFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Compress/LZ/%.cpp + printf " HOSTCXX $(subst $(obj)/,,$(@))\n" + $(HOSTCXX) $(HOSTCXXFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Compress/RangeCoder/%.cpp + printf " HOSTCXX $(subst $(obj)/,,$(@))\n" + $(HOSTCXX) $(HOSTCXXFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Decompress/%.cpp + printf " HOSTCXX $(subst $(obj)/,,$(@))\n" + $(HOSTCXX) $(HOSTCXXFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/7zip/Common/%.cpp + printf " HOSTCXX $(subst $(obj)/,,$(@))\n" + $(HOSTCXX) $(HOSTCXXFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/C/Common/%.cpp + printf " HOSTCXX $(subst $(obj)/,,$(@))\n" + $(HOSTCXX) $(HOSTCXXFLAGS) -o $@ -c $< + +$(tobj)/lzma/%.o: $(tsrc)/lzma/%.cc + printf " HOSTCXX $(subst $(obj)/,,$(@))\n" + $(HOSTCXX) $(HOSTCXXFLAGS) -o $@ -c $< + +endif diff --git a/util/cbfstool/lzma/minilzma.cc b/util/cbfstool/lzma/minilzma.cc new file mode 100644 index 0000000000..5437b59946 --- /dev/null +++ b/util/cbfstool/lzma/minilzma.cc @@ -0,0 +1,318 @@ +/* + * minimal lzma implementation + * + * Copyright (C) 2002 Eric Biederman + * Copyright (C) 2005 Joel Yliluoma + * Copyright (C) 2007 coresystems GmbH + * (Adapted by Stefan Reinauer for coresystems GmbH) + * Copyright (C) 2007 Patrick Georgi + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA, 02110-1301 USA + */ + +#include "C/Common/MyInitGuid.h" +#include "C/7zip/Compress/LZMA/LZMAEncoder.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +const std::vector LZMACompress + (const std::vector& buf); + +const std::vector LZMADeCompress + (const std::vector& buf); + +static inline uint16_t R16(const void* p) +{ + const unsigned char* data = (const unsigned char*)p; + return (data[0] << 0) | (data[1] << 8); +} +static inline uint32_t R32(const void* p) +{ + const unsigned char* data = (const unsigned char*)p; + return R16(data) | (R16(data+2) << 16); +} + +#define L (uint64_t) + +static inline uint64_t R64(const void* p) +{ + const unsigned char* data = (const unsigned char*)p; + return (L R32(data)) | ((L R32(data+4)) << 32); +} + +#undef L + +static UInt32 SelectDictionarySizeFor(unsigned datasize) +{ + #if 1 + return datasize; + #else +#ifdef __GNUC__ + /* gnu c can optimize this switch statement into a fast binary + * search, but it cannot do so for the list of the if statements. + */ + switch(datasize) + { + case 0 ... 512 : return 512; + case 513 ... 1024: return 2048; + case 1025 ... 4096: return 8192; + case 4097 ... 16384: return 32768; + case 16385 ... 65536: return 528288; + case 65537 ... 528288: return 1048576*4; + case 528289 ... 786432: return 1048576*16; + default: return 1048576*32; + } +#else + if(datasize <= 512) return 512; + if(datasize <= 1024) return 1024; + if(datasize <= 4096) return 4096; + if(datasize <= 16384) return 32768; + if(datasize <= 65536) return 528288; + if(datasize <= 528288) return 1048576*4; + if(datasize <= 786432) reutrn 1048576*16; + return 32*1048576; +#endif + #endif +} + + +class CInStreamRam: public ISequentialInStream, public CMyUnknownImp +{ + const std::vector& input; + size_t Pos; +public: + MY_UNKNOWN_IMP + + CInStreamRam(const std::vector& buf) : input(buf), Pos(0) + { + } + virtual ~CInStreamRam() {} + + STDMETHOD(Read)(void *data, UInt32 size, UInt32 *processedSize); +}; + +STDMETHODIMP CInStreamRam::Read(void *data, UInt32 size, UInt32 *processedSize) +{ + UInt32 remain = input.size() - Pos; + if (size > remain) size = remain; + + std::memcpy(data, &input[Pos], size); + Pos += size; + + if(processedSize != NULL) *processedSize = size; + + return S_OK; +} + +class COutStreamRam: public ISequentialOutStream, public CMyUnknownImp +{ + std::vector result; + size_t Pos; +public: + MY_UNKNOWN_IMP + + COutStreamRam(): result(), Pos(0) { } + virtual ~COutStreamRam() { } + + void Reserve(unsigned n) { result.reserve(n); } + const std::vector& Get() const { return result; } + + HRESULT WriteByte(Byte b) + { + if(Pos >= result.size()) result.resize(Pos+1); + result[Pos++] = b; + return S_OK; + } + + STDMETHOD(Write)(const void *data, UInt32 size, UInt32 *processedSize); +}; + +STDMETHODIMP COutStreamRam::Write(const void *data, UInt32 size, UInt32 *processedSize) +{ + if(Pos+size > result.size()) result.resize(Pos+size); + + std::memcpy(&result[Pos], data, size); + if(processedSize != NULL) *processedSize = size; + Pos += size; + return S_OK; +} + +const std::vector LZMACompress(const std::vector& buf) +{ + if(buf.empty()) return buf; + + const UInt32 dictionarysize = SelectDictionarySizeFor(buf.size()); + + NCompress::NLZMA::CEncoder *encoderSpec = new NCompress::NLZMA::CEncoder; + CMyComPtr encoder = encoderSpec; + const PROPID propIDs[] = + { + NCoderPropID::kAlgorithm, + NCoderPropID::kDictionarySize, + NCoderPropID::kNumFastBytes, + }; + const unsigned kNumProps = sizeof(propIDs) / sizeof(propIDs[0]); + PROPVARIANT properties[kNumProps]; + properties[0].vt = VT_UI4; properties[0].ulVal = (UInt32)2; + properties[1].vt = VT_UI4; properties[1].ulVal = (UInt32)dictionarysize; + properties[2].vt = VT_UI4; properties[2].ulVal = (UInt32)64; + + if (encoderSpec->SetCoderProperties(propIDs, properties, kNumProps) != S_OK) + { + Error: + return std::vector (); + } + + COutStreamRam *const outStreamSpec = new COutStreamRam; + CMyComPtr outStream = outStreamSpec; + CInStreamRam *const inStreamSpec = new CInStreamRam(buf); + CMyComPtr inStream = inStreamSpec; + + outStreamSpec->Reserve(buf.size()); + + if (encoderSpec->WriteCoderProperties(outStream) != S_OK) goto Error; + + for (unsigned i = 0; i < 8; i++) + { + UInt64 t = (UInt64)buf.size(); + outStreamSpec->WriteByte((Byte)((t) >> (8 * i))); + } + + HRESULT lzmaResult = encoder->Code(inStream, outStream, 0, 0, 0); + if (lzmaResult != S_OK) goto Error; + + return outStreamSpec->Get(); +} + +#undef RC_NORMALIZE + +#include "C/7zip/Decompress/LzmaDecode.h" +#include "C/7zip/Decompress/LzmaDecode.c" + +const std::vector LZMADeCompress + (const std::vector& buf) +{ + if(buf.size() <= 5+8) return std::vector (); + + uint_least64_t out_sizemax = R64(&buf[5]); + + std::vector result(out_sizemax); + + CLzmaDecoderState state; + LzmaDecodeProperties(&state.Properties, &buf[0], LZMA_PROPERTIES_SIZE); + state.Probs = new CProb[LzmaGetNumProbs(&state.Properties)]; + + SizeT in_done; + SizeT out_done; + LzmaDecode(&state, &buf[13], buf.size()-13, &in_done, + &result[0], result.size(), &out_done); + + delete[] state.Probs; + + result.resize(out_done); + return result; +} + +#ifndef COMPACT +int main(int argc, char *argv[]) +{ + char *s; + FILE *f, *infile, *outfile; + int c; + + if (argc != 4) { + std::fprintf(stderr, "'lzma e file1 file2' encodes file1 into file2.\n" + "'lzma d file2 file1' decodes file2 into file1.\n"); + + return EXIT_FAILURE; + } + if (argc == 4) { + if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL) + || (s = argv[2], (infile = fopen(s, "rb")) == NULL) + || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) { + std::fprintf(stderr, "??? %s\n", s); + return EXIT_FAILURE; + } + } + + struct stat fs; + int si; + if (fstat(fileno(infile), &fs)) { + std::perror(strerror(errno)); + return EXIT_FAILURE; + } + si=fs.st_size; + + char *Buf=(char *)malloc(si); + fread(Buf,si, 1, infile); + + std::vector result; + if (toupper(*argv[1]) == 'E') + result = LZMACompress(std::vector(Buf,Buf+si)); + else + result = LZMADeCompress(std::vector(Buf,Buf+si)); + + fwrite(&result[0], result.size(), 1, outfile); + fclose(infile); + fclose(outfile); + return EXIT_SUCCESS; +} +#else +extern "C" { + +/** + * Compress a buffer with lzma + * Don't copy the result back if it is too large. + * @param in a pointer to the buffer + * @param in_len the length in bytes + * @param out a pointer to a buffer of at least size in_len + * @param out_len a pointer to the compressed length of in + */ + +void do_lzma_compress(char *in, int in_len, char *out, int *out_len) { + std::vector result; + result = LZMACompress(std::vector(in, in + in_len)); + *out_len = result.size(); + if (*out_len < in_len) + std::memcpy(out, &result[0], *out_len); +} + +void do_lzma_uncompress(char *dst, int dst_len, char *src, int src_len) { + std::vector result; + result = LZMADeCompress(std::vector(src, src + src_len)); + if (result.size() <= (SizeT)dst_len) + std::memcpy(dst, &result[0], result.size()); + else + { + fprintf(stderr, "Not copying %d bytes to %d-byte buffer!\n", + (unsigned int)result.size(), dst_len); + exit(1); + } +} + +} +#endif + -- cgit v1.2.3