diff options
Diffstat (limited to 'release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain')
6 files changed, 475 insertions, 0 deletions
diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC.h new file mode 100644 index 00000000..53f3e217 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC.h @@ -0,0 +1,55 @@ +// HC.h
+
+#include "../LZInWindow.h"
+#include "../IMatchFinder.h"
+
+namespace HC_NAMESPACE {
+
+typedef UInt32 CIndex;
+const UInt32 kMaxValForNormalize = (UInt32(1) << 31) - 1;
+
+class CMatchFinderHC:
+ public IMatchFinder,
+ public IMatchFinderSetCallback,
+ public CLZInWindow,
+ public CMyUnknownImp
+{
+ UInt32 _cyclicBufferPos;
+ UInt32 _cyclicBufferSize; // it must be historySize + 1
+ UInt32 _matchMaxLen;
+ CIndex *_hash;
+ UInt32 _cutValue;
+
+ CMyComPtr<IMatchFinderCallback> m_Callback;
+
+ void Normalize();
+ void FreeThisClassMemory();
+ void FreeMemory();
+
+ MY_UNKNOWN_IMP1(IMatchFinderSetCallback)
+
+ STDMETHOD(Init)(ISequentialInStream *inStream);
+ STDMETHOD_(void, ReleaseStream)();
+ STDMETHOD(MovePos)();
+ STDMETHOD_(Byte, GetIndexByte)(Int32 index);
+ STDMETHOD_(UInt32, GetMatchLen)(Int32 index, UInt32 back, UInt32 limit);
+ STDMETHOD_(UInt32, GetNumAvailableBytes)();
+ STDMETHOD_(const Byte *, GetPointerToCurrentPos)();
+ STDMETHOD(Create)(UInt32 historySize, UInt32 keepAddBufferBefore,
+ UInt32 matchMaxLen, UInt32 keepAddBufferAfter);
+ STDMETHOD_(UInt32, GetLongestMatch)(UInt32 *distances);
+ STDMETHOD_(void, DummyLongestMatch)();
+
+ // IMatchFinderSetCallback
+ STDMETHOD(SetCallback)(IMatchFinderCallback *callback);
+
+ virtual void BeforeMoveBlock();
+ virtual void AfterMoveBlock();
+
+public:
+ CMatchFinderHC();
+ virtual ~CMatchFinderHC();
+ void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; }
+};
+
+}
diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC2.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC2.h new file mode 100644 index 00000000..7211cc50 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC2.h @@ -0,0 +1,13 @@ +// HC2.h
+
+#ifndef __HC2_H
+#define __HC2_H
+
+#undef HC_NAMESPACE
+#define HC_NAMESPACE NHC2
+
+#include "HCMF.h"
+#include "HCMFMain.h"
+
+#endif
+
diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC3.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC3.h new file mode 100644 index 00000000..38f05d23 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC3.h @@ -0,0 +1,17 @@ +// HC3.h
+
+#ifndef __HC3_H
+#define __HC3_H
+
+#undef HC_NAMESPACE
+#define HC_NAMESPACE NHC3
+
+#define HASH_ARRAY_2
+
+#include "HC.h"
+#include "HCMain.h"
+
+#undef HASH_ARRAY_2
+
+#endif
+
diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC4.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC4.h new file mode 100644 index 00000000..7d4e2117 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC4.h @@ -0,0 +1,19 @@ +// HC4.h
+
+#ifndef __HC4_H
+#define __HC4_H
+
+#undef HC_NAMESPACE
+#define HC_NAMESPACE NHC4
+
+#define HASH_ARRAY_2
+#define HASH_ARRAY_3
+
+#include "HC.h"
+#include "HCMain.h"
+
+#undef HASH_ARRAY_2
+#undef HASH_ARRAY_3
+
+#endif
+
diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC4b.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC4b.h new file mode 100644 index 00000000..229e5fdf --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC4b.h @@ -0,0 +1,21 @@ +// HC4b.h
+
+#ifndef __HC4B__H
+#define __HC4B__H
+
+#undef HC_NAMESPACE
+#define HC_NAMESPACE NHC4b
+
+#define HASH_ARRAY_2
+#define HASH_ARRAY_3
+#define HASH_BIG
+
+#include "HC.h"
+#include "HCMain.h"
+
+#undef HASH_ARRAY_2
+#undef HASH_ARRAY_3
+#undef HASH_BIG
+
+#endif
+
diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h new file mode 100644 index 00000000..61d932cb --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h @@ -0,0 +1,350 @@ +// HC.h
+
+#include "../../../../Common/Defs.h"
+#include "../../../../Common/CRC.h"
+#include "../../../../Common/Alloc.h"
+
+namespace HC_NAMESPACE {
+
+#ifdef HASH_ARRAY_2
+ static const UInt32 kHash2Size = 1 << 10;
+ #ifdef HASH_ARRAY_3
+ static const UInt32 kNumHashDirectBytes = 0;
+ static const UInt32 kNumHashBytes = 4;
+ static const UInt32 kHash3Size = 1 << 18;
+ #ifdef HASH_BIG
+ static const UInt32 kHashSize = 1 << 23;
+ #else
+ static const UInt32 kHashSize = 1 << 20;
+ #endif
+ #else
+ static const UInt32 kNumHashDirectBytes = 0;
+ static const UInt32 kNumHashBytes = 3;
+ static const UInt32 kHashSize = 1 << (16);
+ #endif
+#else
+ #ifdef HASH_ZIP
+ static const UInt32 kNumHashDirectBytes = 0;
+ static const UInt32 kNumHashBytes = 3;
+ static const UInt32 kHashSize = 1 << 16;
+ #else
+ #define THERE_ARE_DIRECT_HASH_BYTES
+ static const UInt32 kNumHashDirectBytes = 2;
+ static const UInt32 kNumHashBytes = 2;
+ static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
+ #endif
+#endif
+
+static const UInt32 kHashSizeSum = kHashSize
+ #ifdef HASH_ARRAY_2
+ + kHash2Size
+ #ifdef HASH_ARRAY_3
+ + kHash3Size
+ #endif
+ #endif
+ ;
+
+#ifdef HASH_ARRAY_2
+static const UInt32 kHash2Offset = kHashSize;
+#ifdef HASH_ARRAY_3
+static const UInt32 kHash3Offset = kHashSize + kHash2Size;
+#endif
+#endif
+
+CMatchFinderHC::CMatchFinderHC():
+ _hash(0),
+ _cutValue(16)
+{
+}
+
+void CMatchFinderHC::FreeThisClassMemory()
+{
+ BigFree(_hash);
+ _hash = 0;
+}
+
+void CMatchFinderHC::FreeMemory()
+{
+ FreeThisClassMemory();
+ CLZInWindow::Free();
+}
+
+CMatchFinderHC::~CMatchFinderHC()
+{
+ FreeMemory();
+}
+
+STDMETHODIMP CMatchFinderHC::Create(UInt32 historySize, UInt32 keepAddBufferBefore,
+ UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
+{
+ UInt32 sizeReserv = (historySize + keepAddBufferBefore +
+ matchMaxLen + keepAddBufferAfter) / 2 + 256;
+ if (CLZInWindow::Create(historySize + keepAddBufferBefore,
+ matchMaxLen + keepAddBufferAfter, sizeReserv))
+ {
+ if (historySize + 256 > kMaxValForNormalize)
+ {
+ FreeMemory();
+ return E_INVALIDARG;
+ }
+ _matchMaxLen = matchMaxLen;
+ UInt32 newCyclicBufferSize = historySize + 1;
+ if (_hash != 0 && newCyclicBufferSize == _cyclicBufferSize)
+ return S_OK;
+ FreeThisClassMemory();
+ _cyclicBufferSize = newCyclicBufferSize; // don't change it
+ _hash = (CIndex *)BigAlloc((kHashSizeSum + _cyclicBufferSize) * sizeof(CIndex));
+ if (_hash != 0)
+ return S_OK;
+ }
+ FreeMemory();
+ return E_OUTOFMEMORY;
+}
+
+static const UInt32 kEmptyHashValue = 0;
+
+STDMETHODIMP CMatchFinderHC::Init(ISequentialInStream *stream)
+{
+ RINOK(CLZInWindow::Init(stream));
+ for(UInt32 i = 0; i < kHashSizeSum; i++)
+ _hash[i] = kEmptyHashValue;
+ _cyclicBufferPos = 0;
+ ReduceOffsets(-1);
+ return S_OK;
+}
+
+STDMETHODIMP_(void) CMatchFinderHC::ReleaseStream()
+{
+ // ReleaseStream();
+}
+
+#ifdef HASH_ARRAY_2
+#ifdef HASH_ARRAY_3
+inline UInt32 Hash(const Byte *pointer, UInt32 &hash2Value, UInt32 &hash3Value)
+{
+ UInt32 temp = CCRC::Table[pointer[0]] ^ pointer[1];
+ hash2Value = temp & (kHash2Size - 1);
+ hash3Value = (temp ^ (UInt32(pointer[2]) << 8)) & (kHash3Size - 1);
+ return (temp ^ (UInt32(pointer[2]) << 8) ^ (CCRC::Table[pointer[3]] << 5)) &
+ (kHashSize - 1);
+}
+#else // no HASH_ARRAY_3
+inline UInt32 Hash(const Byte *pointer, UInt32 &hash2Value)
+{
+ UInt32 temp = CCRC::Table[pointer[0]] ^ pointer[1];
+ hash2Value = temp & (kHash2Size - 1);
+ return (temp ^ (UInt32(pointer[2]) << 8)) & (kHashSize - 1);;
+}
+#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_(UInt32) CMatchFinderHC::GetLongestMatch(UInt32 *distances)
+{
+ UInt32 lenLimit;
+ if (_pos + _matchMaxLen <= _streamPos)
+ lenLimit = _matchMaxLen;
+ else
+ {
+ lenLimit = _streamPos - _pos;
+ if(lenLimit < kNumHashBytes)
+ return 0;
+ }
+
+ UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
+ Byte *cur = _buffer + _pos;
+
+ UInt32 maxLen = 0;
+
+ #ifdef HASH_ARRAY_2
+ UInt32 hash2Value;
+ #ifdef HASH_ARRAY_3
+ UInt32 hash3Value;
+ UInt32 hashValue = Hash(cur, hash2Value, hash3Value);
+ #else
+ UInt32 hashValue = Hash(cur, hash2Value);
+ #endif
+ #else
+ UInt32 hashValue = Hash(cur);
+ #endif
+ #ifdef HASH_ARRAY_2
+
+ UInt32 curMatch2 = _hash[kHash2Offset + hash2Value];
+ _hash[kHash2Offset + hash2Value] = _pos;
+ distances[2] = 0xFFFFFFFF;
+ if(curMatch2 > matchMinPos)
+ if (_buffer[curMatch2] == cur[0])
+ {
+ distances[2] = _pos - curMatch2 - 1;
+ maxLen = 2;
+ }
+
+ #ifdef HASH_ARRAY_3
+
+ UInt32 curMatch3 = _hash[kHash3Offset + hash3Value];
+ _hash[kHash3Offset + hash3Value] = _pos;
+ distances[3] = 0xFFFFFFFF;
+ if(curMatch3 > matchMinPos)
+ if (_buffer[curMatch3] == cur[0])
+ {
+ distances[3] = _pos - curMatch3 - 1;
+ maxLen = 3;
+ }
+
+ #endif
+ #endif
+
+ UInt32 curMatch = _hash[hashValue];
+ _hash[hashValue] = _pos;
+ CIndex *chain = _hash + kHashSizeSum;
+ chain[_cyclicBufferPos] = curMatch;
+ distances[kNumHashBytes] = 0xFFFFFFFF;
+ #ifdef THERE_ARE_DIRECT_HASH_BYTES
+ if (lenLimit == kNumHashDirectBytes)
+ {
+ if(curMatch > matchMinPos)
+ while (maxLen < kNumHashDirectBytes)
+ distances[++maxLen] = _pos - curMatch - 1;
+ }
+ else
+ #endif
+ {
+ UInt32 count = _cutValue;
+ do
+ {
+ if(curMatch <= matchMinPos)
+ break;
+ Byte *pby1 = _buffer + curMatch;
+ UInt32 currentLen = kNumHashDirectBytes;
+ do
+ {
+ if (pby1[currentLen] != cur[currentLen])
+ break;
+ }
+ while(++currentLen != lenLimit);
+
+ UInt32 delta = _pos - curMatch;
+ while (maxLen < currentLen)
+ distances[++maxLen] = delta - 1;
+ if(currentLen == lenLimit)
+ break;
+
+ UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?
+ (_cyclicBufferPos - delta):
+ (_cyclicBufferPos - delta + _cyclicBufferSize);
+
+ curMatch = chain[cyclicPos];
+ }
+ while(--count != 0);
+ }
+ #ifdef HASH_ARRAY_2
+ #ifdef HASH_ARRAY_3
+ if (distances[4] < distances[3])
+ distances[3] = distances[4];
+ #endif
+ if (distances[3] < distances[2])
+ distances[2] = distances[3];
+ #endif
+ return maxLen;
+}
+
+STDMETHODIMP_(void) CMatchFinderHC::DummyLongestMatch()
+{
+ if (_streamPos - _pos < kNumHashBytes)
+ return;
+
+ Byte *cur = _buffer + _pos;
+
+ #ifdef HASH_ARRAY_2
+ UInt32 hash2Value;
+ #ifdef HASH_ARRAY_3
+ UInt32 hash3Value;
+ UInt32 hashValue = Hash(cur, hash2Value, hash3Value);
+ _hash[kHash3Offset + hash3Value] = _pos;
+ #else
+ UInt32 hashValue = Hash(cur, hash2Value);
+ #endif
+ _hash[kHash2Offset + hash2Value] = _pos;
+ #else
+ UInt32 hashValue = Hash(cur);
+ #endif
+
+ _hash[kHashSizeSum + _cyclicBufferPos] = _hash[hashValue];
+ _hash[hashValue] = _pos;
+}
+
+void CMatchFinderHC::Normalize()
+{
+ UInt32 subValue = _pos - _cyclicBufferSize;
+ CIndex *items = _hash;
+ UInt32 numItems = kHashSizeSum + _cyclicBufferSize;
+ for (UInt32 i = 0; i < numItems; i++)
+ {
+ UInt32 value = items[i];
+ if (value <= subValue)
+ value = kEmptyHashValue;
+ else
+ value -= subValue;
+ items[i] = value;
+ }
+ ReduceOffsets(subValue);
+}
+
+STDMETHODIMP CMatchFinderHC::MovePos()
+{
+ if (++_cyclicBufferPos == _cyclicBufferSize)
+ _cyclicBufferPos = 0;
+ RINOK(CLZInWindow::MovePos());
+ if (_pos == kMaxValForNormalize)
+ Normalize();
+ return S_OK;
+}
+
+STDMETHODIMP_(Byte) CMatchFinderHC::GetIndexByte(Int32 index)
+ { return CLZInWindow::GetIndexByte(index); }
+
+STDMETHODIMP_(UInt32) CMatchFinderHC::GetMatchLen(Int32 index,
+ UInt32 back, UInt32 limit)
+ { return CLZInWindow::GetMatchLen(index, back, limit); }
+
+STDMETHODIMP_(UInt32) CMatchFinderHC::GetNumAvailableBytes()
+ { return CLZInWindow::GetNumAvailableBytes(); }
+
+STDMETHODIMP_(const Byte *) CMatchFinderHC::GetPointerToCurrentPos()
+ { return CLZInWindow::GetPointerToCurrentPos(); }
+
+// IMatchFinderSetCallback
+STDMETHODIMP CMatchFinderHC::SetCallback(IMatchFinderCallback *callback)
+{
+ m_Callback = callback;
+ return S_OK;
+}
+
+void CMatchFinderHC::BeforeMoveBlock()
+{
+ if (m_Callback)
+ m_Callback->BeforeChangingBufferPos();
+ CLZInWindow::BeforeMoveBlock();
+}
+
+void CMatchFinderHC::AfterMoveBlock()
+{
+ if (m_Callback)
+ m_Callback->AfterChangingBufferPos();
+ CLZInWindow::AfterMoveBlock();
+}
+
+}
|