-// BinTreeMain.h\r
-\r
-#include "../../../../Common/Defs.h"\r
-#include "../../../../Common/CRC.h"\r
-#include "../../../../Common/Alloc.h"\r
-\r
-#include "BinTree.h"\r
-\r
-// #include <xmmintrin.h>\r
-// It's for prefetch\r
-// But prefetch doesn't give big gain in K8.\r
-\r
-namespace BT_NAMESPACE {\r
-\r
-#ifdef HASH_ARRAY_2\r
- static const UInt32 kHash2Size = 1 << 10;\r
- #define kNumHashDirectBytes 0\r
- #ifdef HASH_ARRAY_3\r
- static const UInt32 kNumHashBytes = 4;\r
- static const UInt32 kHash3Size = 1 << 16;\r
- #else\r
- static const UInt32 kNumHashBytes = 3;\r
- #endif\r
- static const UInt32 kHashSize = 0;\r
- static const UInt32 kMinMatchCheck = kNumHashBytes;\r
- static const UInt32 kStartMaxLen = 1;\r
-#else\r
- #ifdef HASH_ZIP \r
- #define kNumHashDirectBytes 0\r
- static const UInt32 kNumHashBytes = 3;\r
- static const UInt32 kHashSize = 1 << 16;\r
- static const UInt32 kMinMatchCheck = kNumHashBytes;\r
- static const UInt32 kStartMaxLen = 1;\r
- #else\r
- #define kNumHashDirectBytes 2\r
- static const UInt32 kNumHashBytes = 2;\r
- static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);\r
- static const UInt32 kMinMatchCheck = kNumHashBytes + 1;\r
- static const UInt32 kStartMaxLen = 1;\r
- #endif\r
-#endif\r
-\r
-#ifdef HASH_ARRAY_2\r
-#ifdef HASH_ARRAY_3\r
-static const UInt32 kHash3Offset = kHash2Size;\r
-#endif\r
-#endif\r
-\r
-static const UInt32 kFixHashSize = 0\r
- #ifdef HASH_ARRAY_2\r
- + kHash2Size\r
- #ifdef HASH_ARRAY_3\r
- + kHash3Size\r
- #endif\r
- #endif\r
- ;\r
-\r
-CMatchFinder::CMatchFinder():\r
- _hash(0)\r
-{\r
-}\r
-\r
-void CMatchFinder::FreeThisClassMemory()\r
-{\r
- BigFree(_hash);\r
- _hash = 0;\r
-}\r
-\r
-void CMatchFinder::FreeMemory()\r
-{\r
- FreeThisClassMemory();\r
- CLZInWindow::Free();\r
-}\r
-\r
-CMatchFinder::~CMatchFinder()\r
-{ \r
- FreeMemory();\r
-}\r
-\r
-STDMETHODIMP CMatchFinder::Create(UInt32 historySize, UInt32 keepAddBufferBefore, \r
- UInt32 matchMaxLen, UInt32 keepAddBufferAfter)\r
-{\r
- if (historySize > kMaxValForNormalize - 256)\r
- {\r
- FreeMemory();\r
- return E_INVALIDARG;\r
- }\r
- _cutValue = \r
- #ifdef _HASH_CHAIN\r
- 8 + (matchMaxLen >> 2);\r
- #else\r
- 16 + (matchMaxLen >> 1);\r
- #endif\r
- UInt32 sizeReserv = (historySize + keepAddBufferBefore + \r
- matchMaxLen + keepAddBufferAfter) / 2 + 256;\r
- if (CLZInWindow::Create(historySize + keepAddBufferBefore, \r
- matchMaxLen + keepAddBufferAfter, sizeReserv))\r
- {\r
- _matchMaxLen = matchMaxLen;\r
- UInt32 newCyclicBufferSize = historySize + 1;\r
- if (_hash != 0 && newCyclicBufferSize == _cyclicBufferSize)\r
- return S_OK;\r
- FreeThisClassMemory();\r
- _cyclicBufferSize = newCyclicBufferSize; // don't change it\r
-\r
- UInt32 hs = kHashSize;\r
-\r
- #ifdef HASH_ARRAY_2\r
- hs = historySize - 1;\r
- hs |= (hs >> 1);\r
- hs |= (hs >> 2);\r
- hs |= (hs >> 4);\r
- hs |= (hs >> 8);\r
- hs >>= 1;\r
- hs |= 0xFFFF;\r
- if (hs > (1 << 24))\r
- {\r
- #ifdef HASH_ARRAY_3\r
- hs >>= 1;\r
- #else\r
- hs = (1 << 24) - 1;\r
- #endif\r
- }\r
- _hashMask = hs;\r
- hs++;\r
- #endif\r
- _hashSizeSum = hs + kFixHashSize;\r
- UInt32 numItems = _hashSizeSum + _cyclicBufferSize\r
- #ifndef _HASH_CHAIN\r
- * 2\r
- #endif\r
- ;\r
- size_t sizeInBytes = (size_t)numItems * sizeof(CIndex);\r
- if (sizeInBytes / sizeof(CIndex) != numItems)\r
- return E_OUTOFMEMORY;\r
- _hash = (CIndex *)BigAlloc(sizeInBytes);\r
- _son = _hash + _hashSizeSum;\r
- if (_hash != 0)\r
- return S_OK;\r
- }\r
- FreeMemory();\r
- return E_OUTOFMEMORY;\r
-}\r
-\r
-static const UInt32 kEmptyHashValue = 0;\r
-\r
-STDMETHODIMP CMatchFinder::SetStream(ISequentialInStream *stream)\r
-{\r
- CLZInWindow::SetStream(stream);\r
- return S_OK;\r
-}\r
-\r
-STDMETHODIMP CMatchFinder::Init()\r
-{\r
- RINOK(CLZInWindow::Init());\r
- for(UInt32 i = 0; i < _hashSizeSum; i++)\r
- _hash[i] = kEmptyHashValue;\r
- _cyclicBufferPos = 0;\r
- ReduceOffsets(-1);\r
- return S_OK;\r
-}\r
-\r
-STDMETHODIMP_(void) CMatchFinder::ReleaseStream()\r
-{ \r
- // ReleaseStream(); \r
-}\r
-\r
-#ifdef HASH_ARRAY_2\r
-#ifdef HASH_ARRAY_3\r
-\r
-#define HASH_CALC { \\r
- UInt32 temp = CCRC::Table[cur[0]] ^ cur[1]; \\r
- hash2Value = temp & (kHash2Size - 1); \\r
- hash3Value = (temp ^ (UInt32(cur[2]) << 8)) & (kHash3Size - 1); \\r
- hashValue = (temp ^ (UInt32(cur[2]) << 8) ^ (CCRC::Table[cur[3]] << 5)) & _hashMask; }\r
- \r
-#else // no HASH_ARRAY_3\r
-#define HASH_CALC { \\r
- UInt32 temp = CCRC::Table[cur[0]] ^ cur[1]; \\r
- hash2Value = temp & (kHash2Size - 1); \\r
- hashValue = (temp ^ (UInt32(cur[2]) << 8)) & _hashMask; }\r
-#endif // HASH_ARRAY_3\r
-#else // no HASH_ARRAY_2\r
-#ifdef HASH_ZIP \r
-inline UInt32 Hash(const Byte *pointer)\r
-{\r
- return ((UInt32(pointer[0]) << 8) ^ CCRC::Table[pointer[1]] ^ pointer[2]) & (kHashSize - 1);\r
-}\r
-#else // no HASH_ZIP \r
-inline UInt32 Hash(const Byte *pointer)\r
-{\r
- return pointer[0] ^ (UInt32(pointer[1]) << 8);\r
-}\r
-#endif // HASH_ZIP\r
-#endif // HASH_ARRAY_2\r
-\r
-STDMETHODIMP CMatchFinder::GetMatches(UInt32 *distances)\r
-{\r
- UInt32 lenLimit;\r
- if (_pos + _matchMaxLen <= _streamPos)\r
- lenLimit = _matchMaxLen;\r
- else\r
- {\r
- lenLimit = _streamPos - _pos;\r
- if(lenLimit < kMinMatchCheck)\r
- {\r
- distances[0] = 0;\r
- return MovePos(); \r
- }\r
- }\r
-\r
- int offset = 1;\r
-\r
- UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;\r
- const Byte *cur = _buffer + _pos;\r
-\r
- UInt32 maxLen = kStartMaxLen; // to avoid items for len < hashSize;\r
-\r
- #ifdef HASH_ARRAY_2\r
- UInt32 hash2Value;\r
- #ifdef HASH_ARRAY_3\r
- UInt32 hash3Value;\r
- #endif\r
- UInt32 hashValue;\r
- HASH_CALC;\r
- #else\r
- UInt32 hashValue = Hash(cur);\r
- #endif\r
-\r
- UInt32 curMatch = _hash[kFixHashSize + hashValue];\r
- #ifdef HASH_ARRAY_2\r
- UInt32 curMatch2 = _hash[hash2Value];\r
- #ifdef HASH_ARRAY_3\r
- UInt32 curMatch3 = _hash[kHash3Offset + hash3Value];\r
- #endif\r
- _hash[hash2Value] = _pos;\r
- if(curMatch2 > matchMinPos)\r
- if (_buffer[curMatch2] == cur[0])\r
- {\r
- distances[offset++] = maxLen = 2;\r
- distances[offset++] = _pos - curMatch2 - 1;\r
- }\r
-\r
- #ifdef HASH_ARRAY_3\r
- _hash[kHash3Offset + hash3Value] = _pos;\r
- if(curMatch3 > matchMinPos)\r
- if (_buffer[curMatch3] == cur[0])\r
- {\r
- if (curMatch3 == curMatch2)\r
- offset -= 2;\r
- distances[offset++] = maxLen = 3;\r
- distances[offset++] = _pos - curMatch3 - 1;\r
- curMatch2 = curMatch3;\r
- }\r
- #endif\r
- if (offset != 1 && curMatch2 == curMatch)\r
- {\r
- offset -= 2;\r
- maxLen = kStartMaxLen;\r
- }\r
- #endif\r
-\r
- _hash[kFixHashSize + hashValue] = _pos;\r
-\r
- CIndex *son = _son;\r
-\r
- #ifdef _HASH_CHAIN\r
- son[_cyclicBufferPos] = curMatch;\r
- #else\r
- CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1;\r
- CIndex *ptr1 = son + (_cyclicBufferPos << 1);\r
-\r
- UInt32 len0, len1;\r
- len0 = len1 = kNumHashDirectBytes;\r
- #endif\r
-\r
- #if kNumHashDirectBytes != 0\r
- if(curMatch > matchMinPos)\r
- {\r
- if (_buffer[curMatch + kNumHashDirectBytes] != cur[kNumHashDirectBytes])\r
- {\r
- distances[offset++] = maxLen = kNumHashDirectBytes;\r
- distances[offset++] = _pos - curMatch - 1;\r
- }\r
- }\r
- #endif\r
- UInt32 count = _cutValue;\r
- while(true)\r
- {\r
- if(curMatch <= matchMinPos || count-- == 0)\r
- {\r
- #ifndef _HASH_CHAIN\r
- *ptr0 = *ptr1 = kEmptyHashValue;\r
- #endif\r
- break;\r
- }\r
- UInt32 delta = _pos - curMatch;\r
- UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?\r
- (_cyclicBufferPos - delta):\r
- (_cyclicBufferPos - delta + _cyclicBufferSize);\r
- CIndex *pair = son + \r
- #ifdef _HASH_CHAIN\r
- cyclicPos;\r
- #else\r
- (cyclicPos << 1);\r
- #endif\r
- \r
- // _mm_prefetch((const char *)pair, _MM_HINT_T0);\r
- \r
- const Byte *pb = _buffer + curMatch;\r
- UInt32 len = \r
- #ifdef _HASH_CHAIN\r
- kNumHashDirectBytes;\r
- if (pb[maxLen] == cur[maxLen])\r
- #else\r
- MyMin(len0, len1);\r
- #endif\r
- if (pb[len] == cur[len])\r
- {\r
- while(++len != lenLimit)\r
- if (pb[len] != cur[len])\r
- break;\r
- if (maxLen < len)\r
- {\r
- distances[offset++] = maxLen = len;\r
- distances[offset++] = delta - 1;\r
- if (len == lenLimit)\r
- {\r
- #ifndef _HASH_CHAIN\r
- *ptr1 = pair[0];\r
- *ptr0 = pair[1];\r
- #endif\r
- break;\r
- }\r
- }\r
- }\r
- #ifdef _HASH_CHAIN\r
- curMatch = *pair;\r
- #else\r
- if (pb[len] < cur[len])\r
- {\r
- *ptr1 = curMatch;\r
- ptr1 = pair + 1;\r
- curMatch = *ptr1;\r
- len1 = len;\r
- }\r
- else\r
- {\r
- *ptr0 = curMatch;\r
- ptr0 = pair;\r
- curMatch = *ptr0;\r
- len0 = len;\r
- }\r
- #endif\r
- }\r
- distances[0] = offset - 1;\r
- if (++_cyclicBufferPos == _cyclicBufferSize)\r
- _cyclicBufferPos = 0;\r
- RINOK(CLZInWindow::MovePos());\r
- if (_pos == kMaxValForNormalize)\r
- Normalize();\r
- return S_OK;\r
-}\r
-\r
-STDMETHODIMP CMatchFinder::Skip(UInt32 num)\r
-{\r
- do\r
- {\r
- #ifdef _HASH_CHAIN\r
- if (_streamPos - _pos < kNumHashBytes)\r
- {\r
- RINOK(MovePos()); \r
- continue;\r
- }\r
- #else\r
- UInt32 lenLimit;\r
- if (_pos + _matchMaxLen <= _streamPos)\r
- lenLimit = _matchMaxLen;\r
- else\r
- {\r
- lenLimit = _streamPos - _pos;\r
- if(lenLimit < kMinMatchCheck)\r
- {\r
- RINOK(MovePos());\r
- continue;\r
- }\r
- }\r
- UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;\r
- #endif\r
- const Byte *cur = _buffer + _pos;\r
-\r
- #ifdef HASH_ARRAY_2\r
- UInt32 hash2Value;\r
- #ifdef HASH_ARRAY_3\r
- UInt32 hash3Value;\r
- UInt32 hashValue;\r
- HASH_CALC;\r
- _hash[kHash3Offset + hash3Value] = _pos;\r
- #else\r
- UInt32 hashValue;\r
- HASH_CALC;\r
- #endif\r
- _hash[hash2Value] = _pos;\r
- #else\r
- UInt32 hashValue = Hash(cur);\r
- #endif\r
-\r
- UInt32 curMatch = _hash[kFixHashSize + hashValue];\r
- _hash[kFixHashSize + hashValue] = _pos;\r
-\r
- #ifdef _HASH_CHAIN\r
- _son[_cyclicBufferPos] = curMatch;\r
- #else\r
- CIndex *son = _son;\r
- CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1;\r
- CIndex *ptr1 = son + (_cyclicBufferPos << 1);\r
-\r
- UInt32 len0, len1;\r
- len0 = len1 = kNumHashDirectBytes;\r
- UInt32 count = _cutValue;\r
- while(true)\r
- {\r
- if(curMatch <= matchMinPos || count-- == 0)\r
- {\r
- *ptr0 = *ptr1 = kEmptyHashValue;\r
- break;\r
- }\r
- \r
- UInt32 delta = _pos - curMatch;\r
- UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?\r
- (_cyclicBufferPos - delta):\r
- (_cyclicBufferPos - delta + _cyclicBufferSize);\r
- CIndex *pair = son + (cyclicPos << 1);\r
- \r
- // _mm_prefetch((const char *)pair, _MM_HINT_T0);\r
- \r
- const Byte *pb = _buffer + curMatch;\r
- UInt32 len = MyMin(len0, len1);\r
- \r
- if (pb[len] == cur[len])\r
- {\r
- while(++len != lenLimit)\r
- if (pb[len] != cur[len])\r
- break;\r
- if (len == lenLimit)\r
- {\r
- *ptr1 = pair[0];\r
- *ptr0 = pair[1];\r
- break;\r
- }\r
- }\r
- if (pb[len] < cur[len])\r
- {\r
- *ptr1 = curMatch;\r
- ptr1 = pair + 1;\r
- curMatch = *ptr1;\r
- len1 = len;\r
- }\r
- else\r
- {\r
- *ptr0 = curMatch;\r
- ptr0 = pair;\r
- curMatch = *ptr0;\r
- len0 = len;\r
- }\r
- }\r
- #endif\r
- if (++_cyclicBufferPos == _cyclicBufferSize)\r
- _cyclicBufferPos = 0;\r
- RINOK(CLZInWindow::MovePos());\r
- if (_pos == kMaxValForNormalize)\r
- Normalize();\r
- }\r
- while(--num != 0);\r
- return S_OK;\r
-}\r
-\r
-void CMatchFinder::Normalize()\r
-{\r
- UInt32 subValue = _pos - _cyclicBufferSize;\r
- CIndex *items = _hash;\r
- UInt32 numItems = (_hashSizeSum + _cyclicBufferSize \r
- #ifndef _HASH_CHAIN\r
- * 2\r
- #endif\r
- );\r
- for (UInt32 i = 0; i < numItems; i++)\r
- {\r
- UInt32 value = items[i];\r
- if (value <= subValue)\r
- value = kEmptyHashValue;\r
- else\r
- value -= subValue;\r
- items[i] = value;\r
- }\r
- ReduceOffsets(subValue);\r
-}\r
-\r
-HRESULT CMatchFinder::MovePos()\r
-{\r
- if (++_cyclicBufferPos == _cyclicBufferSize)\r
- _cyclicBufferPos = 0;\r
- RINOK(CLZInWindow::MovePos());\r
- if (_pos == kMaxValForNormalize)\r
- Normalize();\r
- return S_OK;\r
-}\r
-\r
-STDMETHODIMP_(Byte) CMatchFinder::GetIndexByte(Int32 index)\r
- { return CLZInWindow::GetIndexByte(index); }\r
-\r
-STDMETHODIMP_(UInt32) CMatchFinder::GetMatchLen(Int32 index, \r
- UInt32 back, UInt32 limit)\r
- { return CLZInWindow::GetMatchLen(index, back, limit); }\r
-\r
-STDMETHODIMP_(UInt32) CMatchFinder::GetNumAvailableBytes()\r
- { return CLZInWindow::GetNumAvailableBytes(); }\r
-\r
-STDMETHODIMP_(const Byte *) CMatchFinder::GetPointerToCurrentPos()\r
- { return CLZInWindow::GetPointerToCurrentPos(); }\r
-\r
-STDMETHODIMP_(Int32) CMatchFinder::NeedChangeBufferPos(UInt32 numCheckBytes)\r
- { return CLZInWindow::NeedMove(numCheckBytes) ? 1: 0; }\r
-\r
-STDMETHODIMP_(void) CMatchFinder::ChangeBufferPos()\r
- { CLZInWindow::MoveBlock();}\r
-\r
-#undef HASH_CALC\r
-#undef kNumHashDirectBytes\r
- \r
-}\r
+// 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
+
+}
projects / coreboot.git / blobdiff