diff options
Diffstat (limited to 'util/cbfstool/tools/lzma/C/7zip/Compress/LZ')
11 files changed, 887 insertions, 0 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 new file mode 100644 index 0000000000..d464d3b59c --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h @@ -0,0 +1,54 @@ +// BinTree.h
+
+#include "../LZInWindow.h"
+#include "../IMatchFinder.h"
+
+namespace BT_NAMESPACE {
+
+typedef UInt32 CIndex;
+const UInt32 kMaxValForNormalize = (UInt32(1) << 31) - 1;
+
+class CMatchFinder:
+ public IMatchFinder,
+ public CLZInWindow,
+ public CMyUnknownImp,
+ public IMatchFinderSetNumPasses
+{
+ UInt32 _cyclicBufferPos;
+ UInt32 _cyclicBufferSize; // it must be historySize + 1
+ UInt32 _matchMaxLen;
+ CIndex *_hash;
+ CIndex *_son;
+ UInt32 _hashMask;
+ UInt32 _cutValue;
+ UInt32 _hashSizeSum;
+
+ void Normalize();
+ void FreeThisClassMemory();
+ void FreeMemory();
+
+ MY_UNKNOWN_IMP
+
+ STDMETHOD(SetStream)(ISequentialInStream *inStream);
+ STDMETHOD_(void, ReleaseStream)();
+ STDMETHOD(Init)();
+ HRESULT MovePos();
+ STDMETHOD_(Byte, GetIndexByte)(Int32 index);
+ STDMETHOD_(UInt32, GetMatchLen)(Int32 index, UInt32 back, UInt32 limit);
+ STDMETHOD_(UInt32, GetNumAvailableBytes)();
+ STDMETHOD_(const Byte *, GetPointerToCurrentPos)();
+ STDMETHOD_(Int32, NeedChangeBufferPos)(UInt32 numCheckBytes);
+ STDMETHOD_(void, ChangeBufferPos)();
+
+ STDMETHOD(Create)(UInt32 historySize, UInt32 keepAddBufferBefore,
+ UInt32 matchMaxLen, UInt32 keepAddBufferAfter);
+ STDMETHOD(GetMatches)(UInt32 *distances);
+ STDMETHOD(Skip)(UInt32 num);
+
+public:
+ CMatchFinder();
+ virtual ~CMatchFinder();
+ virtual void SetNumPasses(UInt32 numPasses) { _cutValue = numPasses; }
+};
+
+}
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h new file mode 100644 index 0000000000..c5b3939e47 --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h @@ -0,0 +1,12 @@ +// BinTree2.h
+
+#ifndef __BINTREE2_H
+#define __BINTREE2_H
+
+#define BT_NAMESPACE NBT2
+
+#include "BinTreeMain.h"
+
+#undef BT_NAMESPACE
+
+#endif
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h new file mode 100644 index 0000000000..74eb73e293 --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h @@ -0,0 +1,16 @@ +// BinTree3.h
+
+#ifndef __BINTREE3_H
+#define __BINTREE3_H
+
+#define BT_NAMESPACE NBT3
+
+#define HASH_ARRAY_2
+
+#include "BinTreeMain.h"
+
+#undef HASH_ARRAY_2
+
+#undef BT_NAMESPACE
+
+#endif
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h new file mode 100644 index 0000000000..62fc242aac --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h @@ -0,0 +1,18 @@ +// BinTree4.h
+
+#ifndef __BINTREE4_H
+#define __BINTREE4_H
+
+#define BT_NAMESPACE NBT4
+
+#define HASH_ARRAY_2
+#define HASH_ARRAY_3
+
+#include "BinTreeMain.h"
+
+#undef HASH_ARRAY_2
+#undef HASH_ARRAY_3
+
+#undef BT_NAMESPACE
+
+#endif
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h new file mode 100644 index 0000000000..61d1121043 --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h @@ -0,0 +1,531 @@ +// BinTreeMain.h
+
+#include "../../../../Common/Defs.h"
+#include "../../../../Common/CRC.h"
+#include "../../../../Common/Alloc.h"
+
+#include "BinTree.h"
+
+// #include <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 new file mode 100644 index 0000000000..949863be5e --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HC4.h @@ -0,0 +1,19 @@ +// HC4.h
+
+#ifndef __HC4_H
+#define __HC4_H
+
+#define BT_NAMESPACE NHC4
+
+#define HASH_ARRAY_2
+#define HASH_ARRAY_3
+
+#include "HCMain.h"
+
+#undef HASH_ARRAY_2
+#undef HASH_ARRAY_3
+
+#undef BT_NAMESPACE
+
+#endif
+
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h new file mode 100644 index 0000000000..fafce39797 --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h @@ -0,0 +1,6 @@ +// HCMain.h
+
+#define _HASH_CHAIN
+#include "../BinTree/BinTreeMain.h"
+#undef _HASH_CHAIN
+
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/IMatchFinder.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/IMatchFinder.h new file mode 100644 index 0000000000..4bbc14f35a --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/IMatchFinder.h @@ -0,0 +1,33 @@ +// MatchFinders/IMatchFinder.h
+
+#ifndef __IMATCHFINDER_H
+#define __IMATCHFINDER_H
+
+struct IInWindowStream: public IUnknown
+{
+ STDMETHOD(SetStream)(ISequentialInStream *inStream) PURE;
+ STDMETHOD_(void, ReleaseStream)() PURE;
+ STDMETHOD(Init)() PURE;
+ STDMETHOD_(Byte, GetIndexByte)(Int32 index) PURE;
+ STDMETHOD_(UInt32, GetMatchLen)(Int32 index, UInt32 distance, UInt32 limit) PURE;
+ STDMETHOD_(UInt32, GetNumAvailableBytes)() PURE;
+ STDMETHOD_(const Byte *, GetPointerToCurrentPos)() PURE;
+ STDMETHOD_(Int32, NeedChangeBufferPos)(UInt32 numCheckBytes) PURE;
+ STDMETHOD_(void, ChangeBufferPos)() PURE;
+};
+
+struct IMatchFinder: public IInWindowStream
+{
+ STDMETHOD(Create)(UInt32 historySize, UInt32 keepAddBufferBefore,
+ UInt32 matchMaxLen, UInt32 keepAddBufferAfter) PURE;
+ STDMETHOD(GetMatches)(UInt32 *distances) PURE;
+ STDMETHOD(Skip)(UInt32 num) PURE;
+};
+
+struct IMatchFinderSetNumPasses
+{
+ //virtual ~IMatchFinderSetNumPasses(){}
+ virtual void SetNumPasses(UInt32 numPasses) PURE;
+};
+
+#endif
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.cpp b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.cpp new file mode 100644 index 0000000000..a0f791173a --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.cpp @@ -0,0 +1,105 @@ +// LZInWindow.cpp
+
+#include "StdAfx.h"
+
+#include "LZInWindow.h"
+#include "../../../Common/MyCom.h"
+#include "../../../Common/Alloc.h"
+
+void CLZInWindow::Free()
+{
+ ::BigFree(_bufferBase);
+ _bufferBase = 0;
+}
+
+bool CLZInWindow::Create(UInt32 keepSizeBefore, UInt32 keepSizeAfter, UInt32 keepSizeReserv)
+{
+ _keepSizeBefore = keepSizeBefore;
+ _keepSizeAfter = keepSizeAfter;
+ UInt32 blockSize = keepSizeBefore + keepSizeAfter + keepSizeReserv;
+ if (_bufferBase == 0 || _blockSize != blockSize)
+ {
+ Free();
+ _blockSize = blockSize;
+ if (_blockSize != 0)
+ _bufferBase = (Byte *)::BigAlloc(_blockSize);
+ }
+ _pointerToLastSafePosition = _bufferBase + _blockSize - keepSizeAfter;
+ if (_blockSize == 0)
+ return true;
+ return (_bufferBase != 0);
+}
+
+void CLZInWindow::SetStream(ISequentialInStream *stream)
+{
+ _stream = stream;
+}
+
+HRESULT CLZInWindow::Init()
+{
+ _buffer = _bufferBase;
+ _pos = 0;
+ _streamPos = 0;
+ _streamEndWasReached = false;
+ return ReadBlock();
+}
+
+/*
+void CLZInWindow::ReleaseStream()
+{
+ _stream.Release();
+}
+*/
+
+///////////////////////////////////////////
+// ReadBlock
+
+// In State:
+// (_buffer + _streamPos) <= (_bufferBase + _blockSize)
+// Out State:
+// _posLimit <= _blockSize - _keepSizeAfter;
+// if(_streamEndWasReached == false):
+// _streamPos >= _pos + _keepSizeAfter
+// _posLimit = _streamPos - _keepSizeAfter;
+// else
+//
+
+HRESULT CLZInWindow::ReadBlock()
+{
+ if(_streamEndWasReached)
+ return S_OK;
+ while(true)
+ {
+ UInt32 size = (UInt32)(_bufferBase - _buffer) + _blockSize - _streamPos;
+ if(size == 0)
+ return S_OK;
+ UInt32 numReadBytes;
+ RINOK(_stream->Read(_buffer + _streamPos, size, &numReadBytes));
+ if(numReadBytes == 0)
+ {
+ _posLimit = _streamPos;
+ const Byte *pointerToPostion = _buffer + _posLimit;
+ if(pointerToPostion > _pointerToLastSafePosition)
+ _posLimit = (UInt32)(_pointerToLastSafePosition - _buffer);
+ _streamEndWasReached = true;
+ return S_OK;
+ }
+ _streamPos += numReadBytes;
+ if(_streamPos >= _pos + _keepSizeAfter)
+ {
+ _posLimit = _streamPos - _keepSizeAfter;
+ return S_OK;
+ }
+ }
+}
+
+void CLZInWindow::MoveBlock()
+{
+ UInt32 offset = (UInt32)(_buffer - _bufferBase) + _pos - _keepSizeBefore;
+ // we need one additional byte, since MovePos moves on 1 byte.
+ if (offset > 0)
+ offset--;
+ UInt32 numBytes = (UInt32)(_buffer - _bufferBase) + _streamPos - offset;
+ memmove(_bufferBase, _bufferBase + offset, numBytes);
+ _buffer -= offset;
+}
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.h new file mode 100644 index 0000000000..87cb8e94fa --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/LZInWindow.h @@ -0,0 +1,87 @@ +// LZInWindow.h
+
+#ifndef __LZ_IN_WINDOW_H
+#define __LZ_IN_WINDOW_H
+
+#include "../../IStream.h"
+
+class CLZInWindow
+{
+ Byte *_bufferBase; // pointer to buffer with data
+ ISequentialInStream *_stream;
+ UInt32 _posLimit; // offset (from _buffer) when new block reading must be done
+ bool _streamEndWasReached; // if (true) then _streamPos shows real end of stream
+ const Byte *_pointerToLastSafePosition;
+protected:
+ Byte *_buffer; // Pointer to virtual Buffer begin
+ UInt32 _blockSize; // Size of Allocated memory block
+ UInt32 _pos; // offset (from _buffer) of curent byte
+ UInt32 _keepSizeBefore; // how many BYTEs must be kept in buffer before _pos
+ UInt32 _keepSizeAfter; // how many BYTEs must be kept buffer after _pos
+ UInt32 _streamPos; // offset (from _buffer) of first not read byte from Stream
+
+ void MoveBlock();
+ HRESULT ReadBlock();
+ void Free();
+public:
+ CLZInWindow(): _bufferBase(0) {}
+ virtual ~CLZInWindow() { Free(); }
+
+ // keepSizeBefore + keepSizeAfter + keepSizeReserv < 4G)
+ bool Create(UInt32 keepSizeBefore, UInt32 keepSizeAfter, UInt32 keepSizeReserv = (1<<17));
+
+ void SetStream(ISequentialInStream *stream);
+ HRESULT Init();
+ // void ReleaseStream();
+
+ Byte *GetBuffer() const { return _buffer; }
+
+ const Byte *GetPointerToCurrentPos() const { return _buffer + _pos; }
+
+ HRESULT MovePos()
+ {
+ _pos++;
+ if (_pos > _posLimit)
+ {
+ const Byte *pointerToPostion = _buffer + _pos;
+ if(pointerToPostion > _pointerToLastSafePosition)
+ MoveBlock();
+ return ReadBlock();
+ }
+ else
+ return S_OK;
+ }
+ Byte GetIndexByte(Int32 index) const { return _buffer[(size_t)_pos + index]; }
+
+ // index + limit have not to exceed _keepSizeAfter;
+ // -2G <= index < 2G
+ UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit) const
+ {
+ if(_streamEndWasReached)
+ if ((_pos + index) + limit > _streamPos)
+ limit = _streamPos - (_pos + index);
+ distance++;
+ const Byte *pby = _buffer + (size_t)_pos + index;
+ UInt32 i;
+ for(i = 0; i < limit && pby[i] == pby[(size_t)i - distance]; i++);
+ return i;
+ }
+
+ UInt32 GetNumAvailableBytes() const { return _streamPos - _pos; }
+
+ void ReduceOffsets(Int32 subValue)
+ {
+ _buffer += subValue;
+ _posLimit -= subValue;
+ _pos -= subValue;
+ _streamPos -= subValue;
+ }
+
+ bool NeedMove(UInt32 numCheckBytes)
+ {
+ UInt32 reserv = _pointerToLastSafePosition - (_buffer + _pos);
+ return (reserv <= numCheckBytes);
+ }
+};
+
+#endif
diff --git a/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/StdAfx.h b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/StdAfx.h new file mode 100644 index 0000000000..3de038a4ff --- /dev/null +++ b/util/cbfstool/tools/lzma/C/7zip/Compress/LZ/StdAfx.h @@ -0,0 +1,6 @@ +// StdAfx.h
+
+#ifndef __STDAFX_H
+#define __STDAFX_H
+
+#endif
|