summaryrefslogtreecommitdiff
path: root/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2008-05-15 16:13:01 +0000
committerKarl Berry <karl@freefriends.org>2008-05-15 16:13:01 +0000
commitfa5d6d5d3ba960b4e51010ee42f03c21e7038901 (patch)
treed24751e5840e888ea33475fd52f1d1a4c205cc02 /Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree
parentbd2d913a35df5a223eab385296046922ecdd1d4e (diff)
delete lzma-utils
git-svn-id: svn://tug.org/texlive/trunk@8162 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree')
-rw-r--r--Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTree.h55
-rw-r--r--Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTree4.h18
-rw-r--r--Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTreeMain.h444
3 files changed, 0 insertions, 517 deletions
diff --git a/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTree.h b/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTree.h
deleted file mode 100644
index dea1a734509..00000000000
--- a/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTree.h
+++ /dev/null
@@ -1,55 +0,0 @@
-// BinTree.h
-
-#include "../LZInWindow.h"
-#include "../IMatchFinder.h"
-
-namespace BT_NAMESPACE {
-
-typedef UInt32 CIndex;
-const UInt32 kMaxValForNormalize = (UInt32(1) << 31) - 1;
-
-class CMatchFinderBinTree:
- 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:
- CMatchFinderBinTree();
- virtual ~CMatchFinderBinTree();
- void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; }
-};
-
-}
diff --git a/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTree4.h b/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTree4.h
deleted file mode 100644
index 7edcc07edf3..00000000000
--- a/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTree4.h
+++ /dev/null
@@ -1,18 +0,0 @@
-// BinTree4.h
-
-#ifndef __BINTREE4_H
-#define __BINTREE4_H
-
-#undef BT_NAMESPACE
-#define BT_NAMESPACE NBT4
-
-#define HASH_ARRAY_2
-#define HASH_ARRAY_3
-
-#include "BinTree.h"
-#include "BinTreeMain.h"
-
-#undef HASH_ARRAY_2
-#undef HASH_ARRAY_3
-
-#endif
diff --git a/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTreeMain.h b/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTreeMain.h
deleted file mode 100644
index 21ba1d7cdbe..00000000000
--- a/Build/source/utils/lzma-utils/src/sdk/7zip/Compress/LZ/BinTree/BinTreeMain.h
+++ /dev/null
@@ -1,444 +0,0 @@
-// BinTreeMain.h
-
-#include "../../../../Common/Defs.h"
-#include "../../../../Common/CRC.h"
-#include "../../../../Common/Alloc.h"
-
-namespace BT_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 = 3;
- static const UInt32 kNumHashBytes = 3;
- static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
- #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
-
-CMatchFinderBinTree::CMatchFinderBinTree():
- _hash(0),
- _cutValue(0xFF)
-{
-}
-
-void CMatchFinderBinTree::FreeThisClassMemory()
-{
- BigFree(_hash);
- _hash = 0;
-}
-
-void CMatchFinderBinTree::FreeMemory()
-{
- FreeThisClassMemory();
- CLZInWindow::Free();
-}
-
-CMatchFinderBinTree::~CMatchFinderBinTree()
-{
- FreeMemory();
-}
-
-STDMETHODIMP CMatchFinderBinTree::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 * 2) * sizeof(CIndex));
- if (_hash != 0)
- return S_OK;
- }
- FreeMemory();
- return E_OUTOFMEMORY;
-}
-
-static const UInt32 kEmptyHashValue = 0;
-
-STDMETHODIMP CMatchFinderBinTree::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) CMatchFinderBinTree::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)
-{
- hash2Value = (CCRC::Table[pointer[0]] ^ pointer[1]) & (kHash2Size - 1);
- return ((UInt32(pointer[0]) << 16)) | ((UInt32(pointer[1]) << 8)) | pointer[2];
-}
-#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) CMatchFinderBinTree::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
-
- UInt32 curMatch = _hash[hashValue];
- #ifdef HASH_ARRAY_2
- UInt32 curMatch2 = _hash[kHash2Offset + hash2Value];
- #ifdef HASH_ARRAY_3
- UInt32 curMatch3 = _hash[kHash3Offset + hash3Value];
- #endif
- _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
- _hash[kHash3Offset + hash3Value] = _pos;
- distances[3] = 0xFFFFFFFF;
- if(curMatch3 > matchMinPos)
- if (_buffer[curMatch3] == cur[0])
- {
- distances[3] = _pos - curMatch3 - 1;
- maxLen = 3;
- }
- #endif
- #endif
-
- _hash[hashValue] = _pos;
-
- CIndex *son = _hash + kHashSizeSum;
- CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1;
- CIndex *ptr1 = son + (_cyclicBufferPos << 1);
-
- distances[kNumHashBytes] = 0xFFFFFFFF;
-
- #ifdef THERE_ARE_DIRECT_HASH_BYTES
- if (lenLimit == kNumHashDirectBytes)
- {
- if(curMatch > matchMinPos)
- while (maxLen < kNumHashDirectBytes)
- distances[++maxLen] = _pos - curMatch - 1;
- // We don't need tree in this case
- }
- else
- #endif
- {
- UInt32 len0, len1;
- len0 = len1 = kNumHashDirectBytes;
- UInt32 count = _cutValue;
- while(true)
- {
- if(curMatch <= matchMinPos || count-- == 0)
- {
- *ptr0 = kEmptyHashValue;
- *ptr1 = kEmptyHashValue;
- break;
- }
- Byte *pb = _buffer + curMatch;
- UInt32 len = MyMin(len0, len1);
- do
- {
- 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 (pb[len] < cur[len])
- {
- *ptr1 = curMatch;
- ptr1 = pair + 1;
- curMatch = *ptr1;
- len1 = len;
- }
- else
- {
- *ptr0 = curMatch;
- ptr0 = pair;
- curMatch = *ptr0;
- len0 = len;
- }
- }
- else
- {
- *ptr1 = pair[0];
- *ptr0 = pair[1];
- break;
- }
- }
- }
- #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) CMatchFinderBinTree::DummyLongestMatch()
-{
- UInt32 lenLimit;
- if (_pos + _matchMaxLen <= _streamPos)
- lenLimit = _matchMaxLen;
- else
- {
- lenLimit = _streamPos - _pos;
- if(lenLimit < kNumHashBytes)
- return;
- }
- UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
- 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
-
- UInt32 curMatch = _hash[hashValue];
- _hash[hashValue] = _pos;
-
- CIndex *son = _hash + kHashSizeSum;
- 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)
- {
- if(curMatch <= matchMinPos || count-- == 0)
- break;
- Byte *pb = _buffer + curMatch;
- UInt32 len = MyMin(len0, len1);
- do
- {
- 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
- {
- *ptr1 = pair[0];
- *ptr0 = pair[1];
- return;
- }
- }
- }
- *ptr0 = kEmptyHashValue;
- *ptr1 = kEmptyHashValue;
-}
-
-void CMatchFinderBinTree::Normalize()
-{
- UInt32 subValue = _pos - _cyclicBufferSize;
- CIndex *items = _hash;
- UInt32 numItems = (kHashSizeSum + _cyclicBufferSize * 2);
- 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 CMatchFinderBinTree::MovePos()
-{
- if (++_cyclicBufferPos == _cyclicBufferSize)
- _cyclicBufferPos = 0;
- RINOK(CLZInWindow::MovePos());
- if (_pos == kMaxValForNormalize)
- Normalize();
- return S_OK;
-}
-
-STDMETHODIMP_(Byte) CMatchFinderBinTree::GetIndexByte(Int32 index)
- { return CLZInWindow::GetIndexByte(index); }
-
-STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetMatchLen(Int32 index,
- UInt32 back, UInt32 limit)
- { return CLZInWindow::GetMatchLen(index, back, limit); }
-
-STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetNumAvailableBytes()
- { return CLZInWindow::GetNumAvailableBytes(); }
-
-STDMETHODIMP_(const Byte *) CMatchFinderBinTree::GetPointerToCurrentPos()
- { return CLZInWindow::GetPointerToCurrentPos(); }
-
-// IMatchFinderSetCallback
-STDMETHODIMP CMatchFinderBinTree::SetCallback(IMatchFinderCallback *callback)
-{
- m_Callback = callback;
- return S_OK;
-}
-
-void CMatchFinderBinTree::BeforeMoveBlock()
-{
- if (m_Callback)
- m_Callback->BeforeChangingBufferPos();
- CLZInWindow::BeforeMoveBlock();
-}
-
-void CMatchFinderBinTree::AfterMoveBlock()
-{
- if (m_Callback)
- m_Callback->AfterChangingBufferPos();
- CLZInWindow::AfterMoveBlock();
-}
-
-}