From 4aca87515a5083ae0e31ce3177189fd43b6d05ac Mon Sep 17 00:00:00 2001 From: Andreas Baumann Date: Sat, 3 Jan 2015 13:58:15 +0100 Subject: patch to Vanilla Tomato 1.28 --- .../lzma/C/7zip/Compress/LZ/HashChain/HCMain.h | 350 +++++++++++++++++++++ 1 file changed, 350 insertions(+) create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h (limited to 'release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h') 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(); +} + +} -- cgit v1.2.3-54-g00ecf