diff options
Diffstat (limited to '7zip/Compress/LZ/BinTree/BinTreeMain.h')
| -rwxr-xr-x | 7zip/Compress/LZ/BinTree/BinTreeMain.h | 505 |
1 files changed, 294 insertions, 211 deletions
diff --git a/7zip/Compress/LZ/BinTree/BinTreeMain.h b/7zip/Compress/LZ/BinTree/BinTreeMain.h index 21ba1d7c..0965ee42 100755 --- a/7zip/Compress/LZ/BinTree/BinTreeMain.h +++ b/7zip/Compress/LZ/BinTree/BinTreeMain.h @@ -4,38 +4,49 @@ #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 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 + static const UInt32 kHash3Size = 1 << 16; #else - static const UInt32 kNumHashDirectBytes = 3; static const UInt32 kNumHashBytes = 3; - static const UInt32 kHashSize = 1 << (8 * kNumHashBytes); #endif + static const UInt32 kHashSize = 0; + static const UInt32 kMinMatchCheck = kNumHashBytes; + static const UInt32 kStartMaxLen = 1; #else #ifdef HASH_ZIP - static const UInt32 kNumHashDirectBytes = 0; + #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 THERE_ARE_DIRECT_HASH_BYTES - static const UInt32 kNumHashDirectBytes = 2; + #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 -static const UInt32 kHashSizeSum = kHashSize +#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 @@ -44,56 +55,86 @@ static const UInt32 kHashSizeSum = kHashSize #endif ; -#ifdef HASH_ARRAY_2 -static const UInt32 kHash2Offset = kHashSize; -#ifdef HASH_ARRAY_3 -static const UInt32 kHash3Offset = kHashSize + kHash2Size; -#endif -#endif - -CMatchFinderBinTree::CMatchFinderBinTree(): - _hash(0), - _cutValue(0xFF) +CMatchFinder::CMatchFinder(): + _hash(0) { } -void CMatchFinderBinTree::FreeThisClassMemory() +void CMatchFinder::FreeThisClassMemory() { BigFree(_hash); _hash = 0; } -void CMatchFinderBinTree::FreeMemory() +void CMatchFinder::FreeMemory() { FreeThisClassMemory(); CLZInWindow::Free(); } -CMatchFinderBinTree::~CMatchFinderBinTree() +CMatchFinder::~CMatchFinder() { FreeMemory(); } -STDMETHODIMP CMatchFinderBinTree::Create(UInt32 historySize, UInt32 keepAddBufferBefore, +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)) { - 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 * 2) * sizeof(CIndex)); + + 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; } @@ -103,44 +144,47 @@ STDMETHODIMP CMatchFinderBinTree::Create(UInt32 historySize, UInt32 keepAddBuffe static const UInt32 kEmptyHashValue = 0; -STDMETHODIMP CMatchFinderBinTree::Init(ISequentialInStream *stream) +STDMETHODIMP CMatchFinder::SetStream(ISequentialInStream *stream) +{ + CLZInWindow::SetStream(stream); + return S_OK; +} + +STDMETHODIMP CMatchFinder::Init() { - RINOK(CLZInWindow::Init(stream)); - for(UInt32 i = 0; i < kHashSizeSum; i++) + RINOK(CLZInWindow::Init()); + for(UInt32 i = 0; i < _hashSizeSum; i++) _hash[i] = kEmptyHashValue; _cyclicBufferPos = 0; ReduceOffsets(-1); return S_OK; } -STDMETHODIMP_(void) CMatchFinderBinTree::ReleaseStream() +STDMETHODIMP_(void) CMatchFinder::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); -} + +#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 -inline UInt32 Hash(const Byte *pointer, UInt32 &hash2Value) -{ - hash2Value = (CCRC::Table[pointer[0]] ^ pointer[1]) & (kHash2Size - 1); - return ((UInt32(pointer[0]) << 16)) | ((UInt32(pointer[1]) << 8)) | pointer[2]; -} +#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); + return ((UInt32(pointer[0]) << 8) ^ CCRC::Table[pointer[1]] ^ pointer[2]) & (kHashSize - 1); } #else // no HASH_ZIP inline UInt32 Hash(const Byte *pointer) @@ -150,7 +194,7 @@ inline UInt32 Hash(const Byte *pointer) #endif // HASH_ZIP #endif // HASH_ARRAY_2 -STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetLongestMatch(UInt32 *distances) +STDMETHODIMP CMatchFinder::GetMatches(UInt32 *distances) { UInt32 lenLimit; if (_pos + _matchMaxLen <= _streamPos) @@ -158,233 +202,284 @@ STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetLongestMatch(UInt32 *distances) else { lenLimit = _streamPos - _pos; - if(lenLimit < kNumHashBytes) - return 0; + if(lenLimit < kMinMatchCheck) + { + distances[0] = 0; + return MovePos(); + } } + int offset = 1; + UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; - Byte *cur = _buffer + _pos; + const Byte *cur = _buffer + _pos; - UInt32 maxLen = 0; + UInt32 maxLen = kStartMaxLen; // to avoid items for len < hashSize; #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 + UInt32 hashValue; + HASH_CALC; #else UInt32 hashValue = Hash(cur); #endif - UInt32 curMatch = _hash[hashValue]; + UInt32 curMatch = _hash[kFixHashSize + hashValue]; #ifdef HASH_ARRAY_2 - UInt32 curMatch2 = _hash[kHash2Offset + hash2Value]; + UInt32 curMatch2 = _hash[hash2Value]; #ifdef HASH_ARRAY_3 UInt32 curMatch3 = _hash[kHash3Offset + hash3Value]; #endif - _hash[kHash2Offset + hash2Value] = _pos; - distances[2] = 0xFFFFFFFF; + _hash[hash2Value] = _pos; if(curMatch2 > matchMinPos) if (_buffer[curMatch2] == cur[0]) { - distances[2] = _pos - curMatch2 - 1; - maxLen = 2; + distances[offset++] = maxLen = 2; + distances[offset++] = _pos - curMatch2 - 1; } #ifdef HASH_ARRAY_3 _hash[kHash3Offset + hash3Value] = _pos; - distances[3] = 0xFFFFFFFF; if(curMatch3 > matchMinPos) if (_buffer[curMatch3] == cur[0]) { - distances[3] = _pos - curMatch3 - 1; - maxLen = 3; + 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[hashValue] = _pos; + _hash[kFixHashSize + hashValue] = _pos; - CIndex *son = _hash + kHashSizeSum; + CIndex *son = _son; + + #ifdef _HASH_CHAIN + son[_cyclicBufferPos] = curMatch; + #else CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1; CIndex *ptr1 = son + (_cyclicBufferPos << 1); - distances[kNumHashBytes] = 0xFFFFFFFF; + UInt32 len0, len1; + len0 = len1 = kNumHashDirectBytes; + #endif - #ifdef THERE_ARE_DIRECT_HASH_BYTES - if (lenLimit == kNumHashDirectBytes) + #if kNumHashDirectBytes != 0 + if(curMatch > matchMinPos) { - if(curMatch > matchMinPos) - while (maxLen < kNumHashDirectBytes) - distances[++maxLen] = _pos - curMatch - 1; - // We don't need tree in this case + if (_buffer[curMatch + kNumHashDirectBytes] != cur[kNumHashDirectBytes]) + { + distances[offset++] = maxLen = kNumHashDirectBytes; + distances[offset++] = _pos - curMatch - 1; + } } - else #endif + UInt32 count = _cutValue; + while(true) { - UInt32 len0, len1; - len0 = len1 = kNumHashDirectBytes; - UInt32 count = _cutValue; - while(true) + if(curMatch <= matchMinPos || count-- == 0) { - if(curMatch <= matchMinPos || count-- == 0) - { - *ptr0 = kEmptyHashValue; - *ptr1 = kEmptyHashValue; - break; - } - Byte *pb = _buffer + curMatch; - UInt32 len = MyMin(len0, len1); - do - { + #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; - } - while(++len != lenLimit); - - UInt32 delta = _pos - curMatch; - while (maxLen < len) - distances[++maxLen] = delta - 1; - - UInt32 cyclicPos = (delta <= _cyclicBufferPos) ? - (_cyclicBufferPos - delta): - (_cyclicBufferPos - delta + _cyclicBufferSize); - CIndex *pair = son + (cyclicPos << 1); - - if (len != lenLimit) + if (maxLen < len) { - if (pb[len] < cur[len]) + distances[offset++] = maxLen = len; + distances[offset++] = delta - 1; + if (len == lenLimit) { - *ptr1 = curMatch; - ptr1 = pair + 1; - curMatch = *ptr1; - len1 = len; - } - else - { - *ptr0 = curMatch; - ptr0 = pair; - curMatch = *ptr0; - len0 = len; + #ifndef _HASH_CHAIN + *ptr1 = pair[0]; + *ptr0 = pair[1]; + #endif + break; } } - else - { - *ptr1 = pair[0]; - *ptr0 = pair[1]; - 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 } - #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; + distances[0] = offset - 1; + if (++_cyclicBufferPos == _cyclicBufferSize) + _cyclicBufferPos = 0; + RINOK(CLZInWindow::MovePos()); + if (_pos == kMaxValForNormalize) + Normalize(); + return S_OK; } -STDMETHODIMP_(void) CMatchFinderBinTree::DummyLongestMatch() +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 < kNumHashBytes) - return; + if(lenLimit < kMinMatchCheck) + { + RINOK(MovePos()); + continue; + } } UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; - Byte *cur = _buffer + _pos; + #endif + const Byte *cur = _buffer + _pos; #ifdef HASH_ARRAY_2 UInt32 hash2Value; #ifdef HASH_ARRAY_3 UInt32 hash3Value; - UInt32 hashValue = Hash(cur, hash2Value, hash3Value); + UInt32 hashValue; + HASH_CALC; _hash[kHash3Offset + hash3Value] = _pos; #else - UInt32 hashValue = Hash(cur, hash2Value); + UInt32 hashValue; + HASH_CALC; #endif - _hash[kHash2Offset + hash2Value] = _pos; + _hash[hash2Value] = _pos; #else UInt32 hashValue = Hash(cur); #endif - UInt32 curMatch = _hash[hashValue]; - _hash[hashValue] = _pos; + UInt32 curMatch = _hash[kFixHashSize + hashValue]; + _hash[kFixHashSize + hashValue] = _pos; - CIndex *son = _hash + kHashSizeSum; + #ifdef _HASH_CHAIN + _son[_cyclicBufferPos] = curMatch; + #else + CIndex *son = _son; CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1; CIndex *ptr1 = son + (_cyclicBufferPos << 1); - #ifdef THERE_ARE_DIRECT_HASH_BYTES - if (lenLimit != kNumHashDirectBytes) - #endif + UInt32 len0, len1; + len0 = len1 = kNumHashDirectBytes; + UInt32 count = _cutValue; + while(true) { - UInt32 len0, len1; - len0 = len1 = kNumHashDirectBytes; - UInt32 count = _cutValue; - while(true) + if(curMatch <= matchMinPos || count-- == 0) { - if(curMatch <= matchMinPos || count-- == 0) - break; - Byte *pb = _buffer + curMatch; - UInt32 len = MyMin(len0, len1); - do - { + *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; - } - while(++len != lenLimit); - - UInt32 delta = _pos - curMatch; - UInt32 cyclicPos = (delta <= _cyclicBufferPos) ? - (_cyclicBufferPos - delta): - (_cyclicBufferPos - delta + _cyclicBufferSize); - CIndex *pair = son + (cyclicPos << 1); - - if (len != lenLimit) - { - if (pb[len] < cur[len]) - { - *ptr1 = curMatch; - ptr1 = pair + 1; - curMatch = *ptr1; - len1 = len; - } - else - { - *ptr0 = curMatch; - ptr0 = pair; - curMatch = *ptr0; - len0 = len; - } - } - else + if (len == lenLimit) { *ptr1 = pair[0]; *ptr0 = pair[1]; - return; + 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(); } - *ptr0 = kEmptyHashValue; - *ptr1 = kEmptyHashValue; + while(--num != 0); + return S_OK; } -void CMatchFinderBinTree::Normalize() +void CMatchFinder::Normalize() { UInt32 subValue = _pos - _cyclicBufferSize; CIndex *items = _hash; - UInt32 numItems = (kHashSizeSum + _cyclicBufferSize * 2); + UInt32 numItems = (_hashSizeSum + _cyclicBufferSize * 2); for (UInt32 i = 0; i < numItems; i++) { UInt32 value = items[i]; @@ -397,7 +492,7 @@ void CMatchFinderBinTree::Normalize() ReduceOffsets(subValue); } -STDMETHODIMP CMatchFinderBinTree::MovePos() +HRESULT CMatchFinder::MovePos() { if (++_cyclicBufferPos == _cyclicBufferSize) _cyclicBufferPos = 0; @@ -407,38 +502,26 @@ STDMETHODIMP CMatchFinderBinTree::MovePos() return S_OK; } -STDMETHODIMP_(Byte) CMatchFinderBinTree::GetIndexByte(Int32 index) +STDMETHODIMP_(Byte) CMatchFinder::GetIndexByte(Int32 index) { return CLZInWindow::GetIndexByte(index); } -STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetMatchLen(Int32 index, +STDMETHODIMP_(UInt32) CMatchFinder::GetMatchLen(Int32 index, UInt32 back, UInt32 limit) { return CLZInWindow::GetMatchLen(index, back, limit); } -STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetNumAvailableBytes() +STDMETHODIMP_(UInt32) CMatchFinder::GetNumAvailableBytes() { return CLZInWindow::GetNumAvailableBytes(); } -STDMETHODIMP_(const Byte *) CMatchFinderBinTree::GetPointerToCurrentPos() +STDMETHODIMP_(const Byte *) CMatchFinder::GetPointerToCurrentPos() { return CLZInWindow::GetPointerToCurrentPos(); } -// IMatchFinderSetCallback -STDMETHODIMP CMatchFinderBinTree::SetCallback(IMatchFinderCallback *callback) -{ - m_Callback = callback; - return S_OK; -} +STDMETHODIMP_(Int32) CMatchFinder::NeedChangeBufferPos(UInt32 numCheckBytes) + { return CLZInWindow::NeedMove(numCheckBytes) ? 1: 0; } -void CMatchFinderBinTree::BeforeMoveBlock() -{ - if (m_Callback) - m_Callback->BeforeChangingBufferPos(); - CLZInWindow::BeforeMoveBlock(); -} +STDMETHODIMP_(void) CMatchFinder::ChangeBufferPos() + { CLZInWindow::MoveBlock();} -void CMatchFinderBinTree::AfterMoveBlock() -{ - if (m_Callback) - m_Callback->AfterChangingBufferPos(); - CLZInWindow::AfterMoveBlock(); -} +#undef HASH_CALC +#undef kNumHashDirectBytes } |