diff options
Diffstat (limited to 'util/cbfstool/tools/lzma/C/7zip/Compress')
21 files changed, 3555 insertions, 3555 deletions
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h index d464d3b59c..b3b3f13a56 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h @@ -1,54 +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; }
-};
-
-}
+// 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/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h index c5b3939e47..74ca8d9d0e 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h @@ -1,12 +1,12 @@ -// BinTree2.h
-
-#ifndef __BINTREE2_H
-#define __BINTREE2_H
-
-#define BT_NAMESPACE NBT2
-
-#include "BinTreeMain.h"
-
-#undef BT_NAMESPACE
-
-#endif
+// BinTree2.h + +#ifndef __BINTREE2_H +#define __BINTREE2_H + +#define BT_NAMESPACE NBT2 + +#include "BinTreeMain.h" + +#undef BT_NAMESPACE + +#endif diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h index 74eb73e293..76bd9ddd43 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h @@ -1,16 +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
+// 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/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h index 62fc242aac..08e2d1ced6 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h @@ -1,18 +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
+// 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/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h index 61d1121043..7a6f621a06 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h @@ -1,531 +1,531 @@ -// BinTreeMain.h
-
-#include "../../../../Common/Defs.h"
-#include "../../../../Common/CRC.h"
-#include "../../../../Common/Alloc.h"
-
-#include "BinTree.h"
-
-// #include <xmmintrin.h>
-// 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
-
-}
+// BinTreeMain.h + +#include "../../../../Common/Defs.h" +#include "../../../../Common/CRC.h" +#include "../../../../Common/Alloc.h" + +#include "BinTree.h" + +// #include <xmmintrin.h> +// 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/tools/lzma/C/7zip/Compress/LZ/HashChain/HC4.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HC4.h index 949863be5e..1fda4ac6ba 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HC4.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HC4.h @@ -1,19 +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
-
+// 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/tools/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h index fafce39797..d509befea0 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h @@ -1,6 +1,6 @@ -// HCMain.h
-
-#define _HASH_CHAIN
-#include "../BinTree/BinTreeMain.h"
-#undef _HASH_CHAIN
-
+// HCMain.h + +#define _HASH_CHAIN +#include "../BinTree/BinTreeMain.h" +#undef _HASH_CHAIN + diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/IMatchFinder.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/IMatchFinder.h index 4bbc14f35a..9459f210d8 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/IMatchFinder.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/IMatchFinder.h @@ -1,33 +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
+// 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/tools/lzma/C/7zip/Compress/LZ/LZInWindow.cpp b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.cpp index a0f791173a..0e65c4254b 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.cpp +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.cpp @@ -1,105 +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;
-}
+// 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/tools/lzma/C/7zip/Compress/LZ/LZInWindow.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.h index 87cb8e94fa..54f2cb7bba 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.h @@ -1,87 +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
+// 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/tools/lzma/C/7zip/Compress/LZ/StdAfx.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/StdAfx.h index 3de038a4ff..3ff6d8a29f 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/StdAfx.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/StdAfx.h @@ -1,6 +1,6 @@ -// StdAfx.h
-
-#ifndef __STDAFX_H
-#define __STDAFX_H
-
-#endif
+// StdAfx.h + +#ifndef __STDAFX_H +#define __STDAFX_H + +#endif diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMA.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMA.h index d53296ee70..7bc4c438af 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMA.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMA.h @@ -1,82 +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
+// 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/tools/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp b/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp index b6a2f7d591..8d8f0a004c 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp @@ -1,1564 +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<IMatchFinder> 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<kNumMoveBits, kNumPosSlotBits> &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;
-}
-
-}}
+// 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<IMatchFinder> 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<kNumMoveBits, kNumPosSlotBits> &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/tools/lzma/C/7zip/Compress/LZMA/LZMAEncoder.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMAEncoder.h index 55ac80c07c..f4c2c15131 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMAEncoder.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/LZMAEncoder.h @@ -1,411 +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<kNumMoveBits> 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<kNumMoveBits, kNumLowBits> _lowCoder[kNumPosStatesEncodingMax];
- NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumMidBits> _midCoder[kNumPosStatesEncodingMax];
- NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumHighBits> _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<IMatchFinder> _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<kNumMoveBits, kNumPosSlotBits> _posSlotEncoder[kNumLenToPosStates];
-
- CMyBitEncoder _posEncoders[kNumFullDistances - kEndPosModelIndex];
- NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumAlignBits> _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
+// 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<kNumMoveBits> 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<kNumMoveBits, kNumLowBits> _lowCoder[kNumPosStatesEncodingMax]; + NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumMidBits> _midCoder[kNumPosStatesEncodingMax]; + NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumHighBits> _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<IMatchFinder> _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<kNumMoveBits, kNumPosSlotBits> _posSlotEncoder[kNumLenToPosStates]; + + CMyBitEncoder _posEncoders[kNumFullDistances - kEndPosModelIndex]; + NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumAlignBits> _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/tools/lzma/C/7zip/Compress/LZMA/StdAfx.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/StdAfx.h index 83fdd22d58..e7fb6986d2 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/StdAfx.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZMA/StdAfx.h @@ -1,8 +1,8 @@ -// StdAfx.h
-
-#ifndef __STDAFX_H
-#define __STDAFX_H
-
-#include "../../../Common/MyWindows.h"
-
-#endif
+// StdAfx.h + +#ifndef __STDAFX_H +#define __STDAFX_H + +#include "../../../Common/MyWindows.h" + +#endif diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoder.h b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoder.h index 9828bc4b94..bbb2ba82d3 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoder.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoder.h @@ -1,205 +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
+// 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/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.cpp b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.cpp index 8d273c8f93..8e4c4d3a9e 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.cpp +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.cpp @@ -1,80 +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;
- }
- */
-}
-
-}}
+// 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/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.h b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.h index 64538e6879..624f887c94 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBit.h @@ -1,120 +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 <int numMoveBits>
-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 <int numMoveBits>
-class CBitEncoder: public CBitModel<numMoveBits>
-{
-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 <int numMoveBits>
-class CBitDecoder: public CBitModel<numMoveBits>
-{
-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
+// 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 <int numMoveBits> +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 <int numMoveBits> +class CBitEncoder: public CBitModel<numMoveBits> +{ +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 <int numMoveBits> +class CBitDecoder: public CBitModel<numMoveBits> +{ +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/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBitTree.h b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBitTree.h index 1fa023f3b8..4f0c78b49d 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBitTree.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderBitTree.h @@ -1,161 +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 <int numMoveBits, int NumBitLevels>
-class CBitTreeEncoder
-{
- CBitEncoder<numMoveBits> 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 <int numMoveBits, int NumBitLevels>
-class CBitTreeDecoder
-{
- CBitDecoder<numMoveBits> 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 <int numMoveBits>
-void ReverseBitTreeEncode(CBitEncoder<numMoveBits> *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 <int numMoveBits>
-UInt32 ReverseBitTreeGetPrice(CBitEncoder<numMoveBits> *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 <int numMoveBits>
-UInt32 ReverseBitTreeDecode(CBitDecoder<numMoveBits> *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
+// 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 <int numMoveBits, int NumBitLevels> +class CBitTreeEncoder +{ + CBitEncoder<numMoveBits> 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 <int numMoveBits, int NumBitLevels> +class CBitTreeDecoder +{ + CBitDecoder<numMoveBits> 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 <int numMoveBits> +void ReverseBitTreeEncode(CBitEncoder<numMoveBits> *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 <int numMoveBits> +UInt32 ReverseBitTreeGetPrice(CBitEncoder<numMoveBits> *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 <int numMoveBits> +UInt32 ReverseBitTreeDecode(CBitDecoder<numMoveBits> *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/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderOpt.h b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderOpt.h index 829fc83d77..668b9a5b0a 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderOpt.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/RangeCoderOpt.h @@ -1,31 +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
+// 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/tools/lzma/C/7zip/Compress/RangeCoder/StdAfx.h b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/StdAfx.h index 21c2fd780c..b637fd4007 100644 --- a/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/StdAfx.h +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/RangeCoder/StdAfx.h @@ -1,6 +1,6 @@ -// StdAfx.h
-
-#ifndef __STDAFX_H
-#define __STDAFX_H
-
-#endif
+// StdAfx.h + +#ifndef __STDAFX_H +#define __STDAFX_H + +#endif |