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/BinTree/BinTree.h | 55 ++ .../lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h | 12 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h | 16 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTree3Z.h | 16 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h | 18 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTree4b.h | 20 + .../lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h | 444 +++++++++ .../lzma/C/7zip/Compress/LZ/HashChain/HC.h | 55 ++ .../lzma/C/7zip/Compress/LZ/HashChain/HC2.h | 13 + .../lzma/C/7zip/Compress/LZ/HashChain/HC3.h | 17 + .../lzma/C/7zip/Compress/LZ/HashChain/HC4.h | 19 + .../lzma/C/7zip/Compress/LZ/HashChain/HC4b.h | 21 + .../lzma/C/7zip/Compress/LZ/HashChain/HCMain.h | 350 ++++++++ .../lzma/C/7zip/Compress/LZ/IMatchFinder.h | 63 ++ .../lzma/C/7zip/Compress/LZ/LZInWindow.cpp | 102 +++ .../squashfs/lzma/C/7zip/Compress/LZ/LZInWindow.h | 84 ++ .../lzma/C/7zip/Compress/LZ/LZOutWindow.cpp | 17 + .../squashfs/lzma/C/7zip/Compress/LZ/LZOutWindow.h | 64 ++ .../lzma/C/7zip/Compress/LZ/Patricia/Pat.h | 318 +++++++ .../lzma/C/7zip/Compress/LZ/Patricia/Pat2.h | 22 + .../lzma/C/7zip/Compress/LZ/Patricia/Pat2H.h | 24 + .../lzma/C/7zip/Compress/LZ/Patricia/Pat2R.h | 20 + .../lzma/C/7zip/Compress/LZ/Patricia/Pat3H.h | 24 + .../lzma/C/7zip/Compress/LZ/Patricia/Pat4H.h | 24 + .../lzma/C/7zip/Compress/LZ/Patricia/PatMain.h | 989 +++++++++++++++++++++ .../squashfs/lzma/C/7zip/Compress/LZ/StdAfx.h | 6 + 26 files changed, 2813 insertions(+) create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree3Z.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree4b.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC2.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC3.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC4.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HC4b.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/HashChain/HCMain.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/IMatchFinder.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZInWindow.cpp create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZInWindow.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZOutWindow.cpp create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZOutWindow.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2H.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2R.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat3H.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat4H.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/PatMain.h create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/StdAfx.h (limited to 'release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ') diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h new file mode 100644 index 00000000..19a1de0e --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree.h @@ -0,0 +1,55 @@ +// 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 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/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h new file mode 100644 index 00000000..9dbe35d6 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree2.h @@ -0,0 +1,12 @@ +// BinTree2.h + +#ifndef __BINTREE2_H +#define __BINTREE2_H + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT2 + +#include "BinTree.h" +#include "BinTreeMain.h" + +#endif diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h new file mode 100644 index 00000000..9a68669f --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree3.h @@ -0,0 +1,16 @@ +// BinTree3.h + +#ifndef __BINTREE3_H +#define __BINTREE3_H + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT3 + +#define HASH_ARRAY_2 + +#include "BinTree.h" +#include "BinTreeMain.h" + +#undef HASH_ARRAY_2 + +#endif diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree3Z.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree3Z.h new file mode 100644 index 00000000..b77de3d9 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree3Z.h @@ -0,0 +1,16 @@ +// BinTree3Z.h + +#ifndef __BINTREE3Z_H +#define __BINTREE3Z_H + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT3Z + +#define HASH_ZIP + +#include "BinTree.h" +#include "BinTreeMain.h" + +#undef HASH_ZIP + +#endif diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h new file mode 100644 index 00000000..bdc4a87b --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree4.h @@ -0,0 +1,18 @@ +// 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/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree4b.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree4b.h new file mode 100644 index 00000000..06f56662 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTree4b.h @@ -0,0 +1,20 @@ +// BinTree4b.h + +#ifndef __BINTREE4B_H +#define __BINTREE4B_H + +#undef BT_NAMESPACE +#define BT_NAMESPACE NBT4B + +#define HASH_ARRAY_2 +#define HASH_ARRAY_3 +#define HASH_BIG + +#include "BinTree.h" +#include "BinTreeMain.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/BinTree/BinTreeMain.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h new file mode 100644 index 00000000..452466a7 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h @@ -0,0 +1,444 @@ +// 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(); +} + +} 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 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(); +} + +} diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/IMatchFinder.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/IMatchFinder.h new file mode 100644 index 00000000..1d9c88f2 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/IMatchFinder.h @@ -0,0 +1,63 @@ +// MatchFinders/IMatchFinder.h + +#ifndef __IMATCHFINDER_H +#define __IMATCHFINDER_H + +// {23170F69-40C1-278A-0000-000200010000} +DEFINE_GUID(IID_IInWindowStream, +0x23170F69, 0x40C1, 0x278A, 0x00, 0x00, 0x00, 0x02, 0x00, 0x01, 0x00, 0x00); +MIDL_INTERFACE("23170F69-40C1-278A-0000-000200010000") +IInWindowStream: public IUnknown +{ + STDMETHOD(Init)(ISequentialInStream *inStream) PURE; + STDMETHOD_(void, ReleaseStream)() PURE; + STDMETHOD(MovePos)() PURE; + STDMETHOD_(Byte, GetIndexByte)(Int32 index) PURE; + STDMETHOD_(UInt32, GetMatchLen)(Int32 index, UInt32 distance, UInt32 limit) PURE; + STDMETHOD_(UInt32, GetNumAvailableBytes)() PURE; + STDMETHOD_(const Byte *, GetPointerToCurrentPos)() PURE; +}; + +// {23170F69-40C1-278A-0000-000200020000} +DEFINE_GUID(IID_IMatchFinder, +0x23170F69, 0x40C1, 0x278A, 0x00, 0x00, 0x00, 0x02, 0x00, 0x02, 0x00, 0x00); +MIDL_INTERFACE("23170F69-40C1-278A-0000-000200020000") +IMatchFinder: public IInWindowStream +{ + STDMETHOD(Create)(UInt32 historySize, UInt32 keepAddBufferBefore, + UInt32 matchMaxLen, UInt32 keepAddBufferAfter) PURE; + STDMETHOD_(UInt32, GetLongestMatch)(UInt32 *distances) PURE; + STDMETHOD_(void, DummyLongestMatch)() PURE; +}; + +// {23170F69-40C1-278A-0000-000200020100} +DEFINE_GUID(IID_IMatchFinderCallback, +0x23170F69, 0x40C1, 0x278A, 0x00, 0x00, 0x00, 0x02, 0x00, 0x02, 0x01, 0x00); +MIDL_INTERFACE("23170F69-40C1-278A-0000-000200020100") +IMatchFinderCallback: public IUnknown +{ + STDMETHOD(BeforeChangingBufferPos)() PURE; + STDMETHOD(AfterChangingBufferPos)() PURE; +}; + +// {23170F69-40C1-278A-0000-000200020200} +DEFINE_GUID(IID_IMatchFinderSetCallback, +0x23170F69, 0x40C1, 0x278A, 0x00, 0x00, 0x00, 0x02, 0x00, 0x02, 0x02, 0x00); +MIDL_INTERFACE("23170F69-40C1-278A-0000-000200020200") +IMatchFinderSetCallback: public IUnknown +{ + STDMETHOD(SetCallback)(IMatchFinderCallback *callback) PURE; +}; + +/* +// {23170F69-40C1-278A-0000-000200030000} +DEFINE_GUID(IID_IInitMatchFinder, +0x23170F69, 0x40C1, 0x278A, 0x00, 0x00, 0x00, 0x02, 0x00, 0x03, 0x00, 0x00); +MIDL_INTERFACE("23170F69-40C1-278A-0000-000200030000") +IMatchFinderInit: public IUnknown +{ + STDMETHOD(InitMatchFinder)(IMatchFinder *matchFinder) PURE; +}; +*/ + +#endif diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZInWindow.cpp b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZInWindow.cpp new file mode 100644 index 00000000..a7b7a387 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZInWindow.cpp @@ -0,0 +1,102 @@ +// LZInWindow.cpp + +#include "StdAfx.h" + +#include "LZInWindow.h" +#include "../../../Common/MyCom.h" +#include "../../../Common/Alloc.h" + +void CLZInWindow::Free() +{ + ::BigFree(_bufferBase); + _bufferBase = 0; +} + +bool CLZInWindow::Create(UInt32 keepSizeBefore, UInt32 keepSizeAfter, UInt32 keepSizeReserv) +{ + _keepSizeBefore = keepSizeBefore; + _keepSizeAfter = keepSizeAfter; + _keepSizeReserv = keepSizeReserv; + UInt32 blockSize = keepSizeBefore + keepSizeAfter + keepSizeReserv; + if (_bufferBase == 0 || _blockSize != blockSize) + { + Free(); + _blockSize = blockSize; + if (_blockSize != 0) + _bufferBase = (Byte *)::BigAlloc(_blockSize); + } + _pointerToLastSafePosition = _bufferBase + _blockSize - keepSizeAfter; + if (_blockSize == 0) + return true; + return (_bufferBase != 0); +} + + +HRESULT CLZInWindow::Init(ISequentialInStream *stream) +{ + _stream = stream; + _buffer = _bufferBase; + _pos = 0; + _streamPos = 0; + _streamEndWasReached = false; + return ReadBlock(); +} + +/* +void CLZInWindow::ReleaseStream() +{ + _stream.Release(); +} +*/ + +/////////////////////////////////////////// +// ReadBlock + +// In State: +// (_buffer + _streamPos) <= (_bufferBase + _blockSize) +// Out State: +// _posLimit <= _blockSize - _keepSizeAfter; +// if(_streamEndWasReached == false): +// _streamPos >= _pos + _keepSizeAfter +// _posLimit = _streamPos - _keepSizeAfter; +// else +// + +HRESULT CLZInWindow::ReadBlock() +{ + if(_streamEndWasReached) + return S_OK; + while(true) + { + UInt32 size = UInt32(_bufferBase - _buffer) + _blockSize - _streamPos; + if(size == 0) + return S_OK; + UInt32 numReadBytes; + RINOK(_stream->Read(_buffer + _streamPos, size, &numReadBytes)); + if(numReadBytes == 0) + { + _posLimit = _streamPos; + const Byte *pointerToPostion = _buffer + _posLimit; + if(pointerToPostion > _pointerToLastSafePosition) + _posLimit = (UInt32)(_pointerToLastSafePosition - _buffer); + _streamEndWasReached = true; + return S_OK; + } + _streamPos += numReadBytes; + if(_streamPos >= _pos + _keepSizeAfter) + { + _posLimit = _streamPos - _keepSizeAfter; + return S_OK; + } + } +} + +void CLZInWindow::MoveBlock() +{ + BeforeMoveBlock(); + UInt32 offset = UInt32(_buffer - _bufferBase) + _pos - _keepSizeBefore; + UInt32 numBytes = UInt32(_buffer - _bufferBase) + _streamPos - offset; + memmove(_bufferBase, _bufferBase + offset, numBytes); + _buffer -= offset; + AfterMoveBlock(); +} diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZInWindow.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZInWindow.h new file mode 100644 index 00000000..7dc194f2 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZInWindow.h @@ -0,0 +1,84 @@ +// LZInWindow.h + +#ifndef __LZ_IN_WINDOW_H +#define __LZ_IN_WINDOW_H + +#include "../../IStream.h" + +class CLZInWindow +{ + Byte *_bufferBase; // pointer to buffer with data + ISequentialInStream *_stream; + UInt32 _posLimit; // offset (from _buffer) of first byte when new block reading must be done + bool _streamEndWasReached; // if (true) then _streamPos shows real end of stream + const Byte *_pointerToLastSafePosition; +protected: + Byte *_buffer; // Pointer to virtual Buffer begin + UInt32 _blockSize; // Size of Allocated memory block + UInt32 _pos; // offset (from _buffer) of curent byte + UInt32 _keepSizeBefore; // how many BYTEs must be kept in buffer before _pos + UInt32 _keepSizeAfter; // how many BYTEs must be kept buffer after _pos + UInt32 _keepSizeReserv; // how many BYTEs must be kept as reserv + UInt32 _streamPos; // offset (from _buffer) of first not read byte from Stream + + virtual void BeforeMoveBlock() {}; + virtual void AfterMoveBlock() {}; + void MoveBlock(); + virtual HRESULT ReadBlock(); + void Free(); +public: + CLZInWindow(): _bufferBase(0) {} + virtual ~CLZInWindow() { Free(); } + + bool Create(UInt32 keepSizeBefore, UInt32 keepSizeAfter, + UInt32 keepSizeReserv = (1<<17)); + + HRESULT Init(ISequentialInStream *stream); + // void ReleaseStream(); + + Byte *GetBuffer() const { return _buffer; } + + const Byte *GetPointerToCurrentPos() const { return _buffer + _pos; } + + HRESULT MovePos() + { + _pos++; + if (_pos > _posLimit) + { + const Byte *pointerToPostion = _buffer + _pos; + if(pointerToPostion > _pointerToLastSafePosition) + MoveBlock(); + return ReadBlock(); + } + else + return S_OK; + } + Byte GetIndexByte(Int32 index)const + { return _buffer[(size_t)_pos + index]; } + + // index + limit have not to exceed _keepSizeAfter; + UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit) const + { + if(_streamEndWasReached) + if ((_pos + index) + limit > _streamPos) + limit = _streamPos - (_pos + index); + distance++; + Byte *pby = _buffer + (size_t)_pos + index; + UInt32 i; + for(i = 0; i < limit && pby[i] == pby[(size_t)i - distance]; i++); + return i; + } + + UInt32 GetNumAvailableBytes() const { return _streamPos - _pos; } + + void ReduceOffsets(Int32 subValue) + { + _buffer += subValue; + _posLimit -= subValue; + _pos -= subValue; + _streamPos -= subValue; + } + +}; + +#endif diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZOutWindow.cpp b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZOutWindow.cpp new file mode 100644 index 00000000..329a7db3 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZOutWindow.cpp @@ -0,0 +1,17 @@ +// LZOutWindow.cpp + +#include "StdAfx.h" + +#include "../../../Common/Alloc.h" +#include "LZOutWindow.h" + +void CLZOutWindow::Init(bool solid) +{ + if(!solid) + COutBuffer::Init(); + #ifdef _NO_EXCEPTIONS + ErrorCode = S_OK; + #endif +} + + diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZOutWindow.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZOutWindow.h new file mode 100644 index 00000000..ba38c5e2 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/LZOutWindow.h @@ -0,0 +1,64 @@ +// LZOutWindow.h + +#ifndef __LZ_OUT_WINDOW_H +#define __LZ_OUT_WINDOW_H + +#include "../../IStream.h" +#include "../../Common/OutBuffer.h" + +/* +#ifndef _NO_EXCEPTIONS +class CLZOutWindowException +{ +public: + HRESULT ErrorCode; + CLZOutWindowException(HRESULT errorCode): ErrorCode(errorCode) {} +}; +#endif +*/ +typedef COutBufferException CLZOutWindowException; + +class CLZOutWindow: public COutBuffer +{ +public: + void Init(bool solid = false); + + // distance >= 0, len > 0, + bool CopyBlock(UInt32 distance, UInt32 len) + { + UInt32 pos = _pos - distance - 1; + if (pos >= _bufferSize) + { + if (!_overDict) + return false; + pos += _bufferSize; + } + do + { + if (pos == _bufferSize) + pos = 0; + _buffer[_pos++] = _buffer[pos++]; + if (_pos == _limitPos) + FlushWithCheck(); + } + while(--len != 0); + return true; + } + + void PutByte(Byte b) + { + _buffer[_pos++] = b; + if (_pos == _limitPos) + FlushWithCheck(); + } + + Byte GetByte(UInt32 distance) const + { + UInt32 pos = _pos - distance - 1; + if (pos >= _bufferSize) + pos += _bufferSize; + return _buffer[pos]; + } +}; + +#endif diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat.h new file mode 100644 index 00000000..2d0ce6d0 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat.h @@ -0,0 +1,318 @@ +// Pat.h + +// #ifndef __PATRICIA__H +// #define __PATRICIA__H + +#include "../../../../Common/MyCom.h" +#include "../../../../Common/Types.h" +#include "../LZInWindow.h" + +namespace PAT_NAMESPACE { + +struct CNode; + +typedef CNode *CNodePointer; + +// #define __AUTO_REMOVE + +// #define __NODE_4_BITS +// #define __NODE_3_BITS +// #define __NODE_2_BITS +// #define __NODE_2_BITS_PADDING + +// #define __HASH_3 + + +typedef UInt32 CIndex; + +#ifdef __NODE_4_BITS + typedef UInt32 CIndex2; + typedef UInt32 CSameBitsType; +#else +#ifdef __NODE_3_BITS + typedef UInt32 CIndex2; + typedef UInt32 CSameBitsType; +#else + + typedef UInt32 CIndex; + typedef UInt32 CSameBitsType; + + typedef CIndex CIndex2; +#endif +#endif + +const UInt32 kNumBitsInIndex = sizeof(CIndex) * 8; +const UInt32 kMatchStartValue = UInt32(1) << (kNumBitsInIndex - 1); +// don't change kMatchStartValue definition, since it is used in +// PatMain.h: + +typedef CIndex CMatchPointer; + +const UInt32 kDescendantEmptyValue = kMatchStartValue - 1; + +union CDescendant +{ + CIndex NodePointer; + CMatchPointer MatchPointer; + bool IsEmpty() const { return NodePointer == kDescendantEmptyValue; } + bool IsNode() const { return NodePointer < kDescendantEmptyValue; } + bool IsMatch() const { return NodePointer > kDescendantEmptyValue; } + void MakeEmpty() { NodePointer = kDescendantEmptyValue; } +}; + +#undef MY_BYTE_SIZE + +#ifdef __NODE_4_BITS + #define MY_BYTE_SIZE 8 + const UInt32 kNumSubBits = 4; +#else +#ifdef __NODE_3_BITS + #define MY_BYTE_SIZE 9 + const UInt32 kNumSubBits = 3; +#else + #define MY_BYTE_SIZE 8 + #ifdef __NODE_2_BITS + const UInt32 kNumSubBits = 2; + #else + const UInt32 kNumSubBits = 1; + #endif +#endif +#endif + +const UInt32 kNumSubNodes = 1 << kNumSubBits; +const UInt32 kSubNodesMask = kNumSubNodes - 1; + +struct CNode +{ + CIndex2 LastMatch; + CSameBitsType NumSameBits; + union + { + CDescendant Descendants[kNumSubNodes]; + UInt32 NextFreeNode; + }; + #ifdef __NODE_2_BITS + #ifdef __NODE_2_BITS_PADDING + UInt32 Padding[2]; + #endif + #endif +}; + +#undef kIDNumBitsByte +#undef kIDNumBitsString + +#ifdef __NODE_4_BITS + #define kIDNumBitsByte 0x30 + #define kIDNumBitsString TEXT("4") +#else +#ifdef __NODE_3_BITS + #define kIDNumBitsByte 0x20 + #define kIDNumBitsString TEXT("3") +#else +#ifdef __NODE_2_BITS + #define kIDNumBitsByte 0x10 + #define kIDNumBitsString TEXT("2") +#else + #define kIDNumBitsByte 0x00 + #define kIDNumBitsString TEXT("1") +#endif +#endif +#endif + +#undef kIDManualRemoveByte +#undef kIDManualRemoveString + +#ifdef __AUTO_REMOVE + #define kIDManualRemoveByte 0x00 + #define kIDManualRemoveString TEXT("") +#else + #define kIDManualRemoveByte 0x08 + #define kIDManualRemoveString TEXT("R") +#endif + +#undef kIDHash3Byte +#undef kIDHash3String + +#ifdef __HASH_3 + #define kIDHash3Byte 0x04 + #define kIDHash3String TEXT("H") +#else + #define kIDHash3Byte 0x00 + #define kIDHash3String TEXT("") +#endif + +#undef kIDUse3BytesByte +#undef kIDUse3BytesString + +#define kIDUse3BytesByte 0x00 +#define kIDUse3BytesString TEXT("") + +#undef kIDPaddingByte +#undef kIDPaddingString + +#ifdef __NODE_2_BITS_PADDING + #define kIDPaddingByte 0x01 + #define kIDPaddingString TEXT("P") +#else + #define kIDPaddingByte 0x00 + #define kIDPaddingString TEXT("") +#endif + + +// #undef kIDString +// #define kIDString TEXT("Compress.MatchFinderPat") kIDNumBitsString kIDManualRemoveString kIDUse3BytesString kIDPaddingString kIDHash3String + +// {23170F69-40C1-278C-01XX-0000000000} + +DEFINE_GUID(PAT_CLSID, +0x23170F69, 0x40C1, 0x278C, 0x01, +kIDNumBitsByte | +kIDManualRemoveByte | kIDHash3Byte | kIDUse3BytesByte | kIDPaddingByte, +0x00, 0x00, 0x00, 0x00, 0x00, 0x00); + +// III(PAT_NAMESPACE) + +class CPatricia: + public IMatchFinder, + public IMatchFinderSetCallback, + public CMyUnknownImp, + CLZInWindow +{ + MY_UNKNOWN_IMP1(IMatchFinderSetCallback) + + STDMETHOD(Init)(ISequentialInStream *aStream); + STDMETHOD_(void, ReleaseStream)(); + STDMETHOD(MovePos)(); + STDMETHOD_(Byte, GetIndexByte)(Int32 index); + STDMETHOD_(UInt32, GetMatchLen)(Int32 index, UInt32 back, UInt32 limit); + STDMETHOD_(UInt32, GetNumAvailableBytes)(); + STDMETHOD(Create)(UInt32 historySize, + UInt32 keepAddBufferBefore, UInt32 matchMaxLen, + UInt32 keepAddBufferAfter); + STDMETHOD_(UInt32, GetLongestMatch)(UInt32 *distances); + STDMETHOD_(void, DummyLongestMatch)(); + STDMETHOD_(const Byte *, GetPointerToCurrentPos)(); + + void FreeMemory(); +public: + CPatricia(); + ~CPatricia(); + + UInt32 _sizeHistory; + UInt32 _matchMaxLen; + + CDescendant *m_HashDescendants; + #ifdef __HASH_3 + CDescendant *m_Hash2Descendants; + #endif + + CNode *m_Nodes; + + UInt32 m_FreeNode; + UInt32 m_FreeNodeMax; + + #ifdef __AUTO_REMOVE + UInt32 m_NumUsedNodes; + UInt32 m_NumNodes; + #else + bool m_SpecialRemoveMode; + #endif + + bool m_SpecialMode; + UInt32 m_NumNotChangedCycles; + UInt32 *m_TmpBacks; + + CMyComPtr m_Callback; + + virtual void BeforeMoveBlock(); + virtual void AfterMoveBlock(); + + // IMatchFinderSetCallback + STDMETHOD(SetCallback)(IMatchFinderCallback *callback); + + void ChangeLastMatch(UInt32 hashValue); + + #ifdef __AUTO_REMOVE + void TestRemoveDescendant(CDescendant &descendant, UInt32 limitPos); + void TestRemoveNodes(); + void RemoveNode(UInt32 index); + void TestRemoveAndNormalizeDescendant(CDescendant &descendant, + UInt32 limitPos, UInt32 subValue); + void TestRemoveNodesAndNormalize(); + #else + void NormalizeDescendant(CDescendant &descendant, UInt32 subValue); + void Normalize(); + void RemoveMatch(); + #endif +private: + void AddInternalNode(CNodePointer aNode, CIndex *aNodePointerPointer, + Byte aByte, Byte aByteXOR, UInt32 aNumSameBits, UInt32 aPos) + { + while((aByteXOR & kSubNodesMask) == 0) + { + aByteXOR >>= kNumSubBits; + aByte >>= kNumSubBits; + aNumSameBits -= kNumSubBits; + } + // Insert New Node + CNodePointer aNewNode = &m_Nodes[m_FreeNode]; + UInt32 aNodeIndex = *aNodePointerPointer; + *aNodePointerPointer = m_FreeNode; + m_FreeNode = aNewNode->NextFreeNode; + #ifdef __AUTO_REMOVE + m_NumUsedNodes++; + #endif + if (m_FreeNode > m_FreeNodeMax) + { + m_FreeNodeMax = m_FreeNode; + m_Nodes[m_FreeNode].NextFreeNode = m_FreeNode + 1; + } + + UInt32 aBitsNew = aByte & kSubNodesMask; + UInt32 aBitsOld = (aByte ^ aByteXOR) & kSubNodesMask; + for (UInt32 i = 0; i < kNumSubNodes; i++) + aNewNode->Descendants[i].NodePointer = kDescendantEmptyValue; + aNewNode->Descendants[aBitsNew].MatchPointer = aPos + kMatchStartValue; + aNewNode->Descendants[aBitsOld].NodePointer = aNodeIndex; + aNewNode->NumSameBits = CSameBitsType(aNode->NumSameBits - aNumSameBits); + aNewNode->LastMatch = aPos; + + aNode->NumSameBits = CSameBitsType(aNumSameBits - kNumSubBits); + } + + void AddLeafNode(CNodePointer aNode, Byte aByte, Byte aByteXOR, + UInt32 aNumSameBits, UInt32 aPos, UInt32 aDescendantIndex) + { + for(;(aByteXOR & kSubNodesMask) == 0; aNumSameBits += kNumSubBits) + { + aByte >>= kNumSubBits; + aByteXOR >>= kNumSubBits; + } + UInt32 aNewNodeIndex = m_FreeNode; + CNodePointer aNewNode = &m_Nodes[m_FreeNode]; + m_FreeNode = aNewNode->NextFreeNode; + #ifdef __AUTO_REMOVE + m_NumUsedNodes++; + #endif + if (m_FreeNode > m_FreeNodeMax) + { + m_FreeNodeMax = m_FreeNode; + m_Nodes[m_FreeNode].NextFreeNode = m_FreeNode + 1; + } + + UInt32 aBitsNew = (aByte & kSubNodesMask); + UInt32 aBitsOld = (aByte ^ aByteXOR) & kSubNodesMask; + for (UInt32 i = 0; i < kNumSubNodes; i++) + aNewNode->Descendants[i].NodePointer = kDescendantEmptyValue; + aNewNode->Descendants[aBitsNew].MatchPointer = aPos + kMatchStartValue; + aNewNode->Descendants[aBitsOld].MatchPointer = + aNode->Descendants[aDescendantIndex].MatchPointer; + aNewNode->NumSameBits = CSameBitsType(aNumSameBits); + aNewNode->LastMatch = aPos; + aNode->Descendants[aDescendantIndex].NodePointer = aNewNodeIndex; + } +}; + +} + +// #endif diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2.h new file mode 100644 index 00000000..0c97164d --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2.h @@ -0,0 +1,22 @@ +// Pat2.h + +#ifndef __PAT2__H +#define __PAT2__H + +#undef PAT_CLSID +#define PAT_CLSID CLSID_CMatchFinderPat2 + +#undef PAT_NAMESPACE +#define PAT_NAMESPACE NPat2 + +#define __AUTO_REMOVE +#define __NODE_2_BITS + +#include "Pat.h" +#include "PatMain.h" + +#undef __AUTO_REMOVE +#undef __NODE_2_BITS + +#endif + diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2H.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2H.h new file mode 100644 index 00000000..c3a374fa --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2H.h @@ -0,0 +1,24 @@ +// Pat2H.h + +#ifndef __PAT2H__H +#define __PAT2H__H + +#undef PAT_CLSID +#define PAT_CLSID CLSID_CMatchFinderPat2H + +#undef PAT_NAMESPACE +#define PAT_NAMESPACE NPat2H + +#define __AUTO_REMOVE +#define __NODE_2_BITS +#define __HASH_3 + +#include "Pat.h" +#include "PatMain.h" + +#undef __AUTO_REMOVE +#undef __NODE_2_BITS +#undef __HASH_3 + +#endif + diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2R.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2R.h new file mode 100644 index 00000000..2c6267e8 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat2R.h @@ -0,0 +1,20 @@ +// Pat2R.h + +#ifndef __PAT2R__H +#define __PAT2R__H + +#undef PAT_CLSID +#define PAT_CLSID CLSID_CMatchFinderPat2R + +#undef PAT_NAMESPACE +#define PAT_NAMESPACE NPat2R + +#define __NODE_2_BITS + +#include "Pat.h" +#include "PatMain.h" + +#undef __NODE_2_BITS + +#endif + diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat3H.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat3H.h new file mode 100644 index 00000000..96bdccd4 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat3H.h @@ -0,0 +1,24 @@ +// Pat3H.h + +#ifndef __PAT3H__H +#define __PAT3H__H + +#undef PAT_CLSID +#define PAT_CLSID CLSID_CMatchFinderPat3H + +#undef PAT_NAMESPACE +#define PAT_NAMESPACE NPat3H + +#define __AUTO_REMOVE +#define __NODE_3_BITS +#define __HASH_3 + +#include "Pat.h" +#include "PatMain.h" + +#undef __AUTO_REMOVE +#undef __NODE_3_BITS +#undef __HASH_3 + +#endif + diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat4H.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat4H.h new file mode 100644 index 00000000..ff5fdbf4 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat4H.h @@ -0,0 +1,24 @@ +// Pat4H.h + +#ifndef __PAT4H__H +#define __PAT4H__H + +#undef PAT_CLSID +#define PAT_CLSID CLSID_CMatchFinderPat4H + +#undef PAT_NAMESPACE +#define PAT_NAMESPACE NPat4H + +#define __AUTO_REMOVE +#define __NODE_4_BITS +#define __HASH_3 + +#include "Pat.h" +#include "PatMain.h" + +#undef __AUTO_REMOVE +#undef __NODE_4_BITS +#undef __HASH_3 + +#endif + diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/PatMain.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/PatMain.h new file mode 100644 index 00000000..028f16ba --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/PatMain.h @@ -0,0 +1,989 @@ +// PatMain.h + +#include "../../../../Common/Defs.h" +#include "../../../../Common/Alloc.h" + +namespace PAT_NAMESPACE { + +STDMETHODIMP CPatricia::SetCallback(IMatchFinderCallback *callback) +{ + m_Callback = callback; + return S_OK; +} + +void CPatricia::BeforeMoveBlock() +{ + if (m_Callback) + m_Callback->BeforeChangingBufferPos(); + CLZInWindow::BeforeMoveBlock(); +} + +void CPatricia::AfterMoveBlock() +{ + if (m_Callback) + m_Callback->AfterChangingBufferPos(); + CLZInWindow::AfterMoveBlock(); +} + +const UInt32 kMatchStartValue2 = 2; +const UInt32 kDescendantEmptyValue2 = kMatchStartValue2 - 1; +const UInt32 kDescendantsNotInitilized2 = kDescendantEmptyValue2 - 1; + +#ifdef __HASH_3 + +static const UInt32 kNumHashBytes = 3; +static const UInt32 kHashSize = 1 << (8 * kNumHashBytes); + +static const UInt32 kNumHash2Bytes = 2; +static const UInt32 kHash2Size = 1 << (8 * kNumHash2Bytes); +static const UInt32 kPrevHashSize = kNumHash2Bytes; + +#else + +static const UInt32 kNumHashBytes = 2; +static const UInt32 kHashSize = 1 << (8 * kNumHashBytes); +static const UInt32 kPrevHashSize = 0; + +#endif + + +CPatricia::CPatricia(): + m_HashDescendants(0), + #ifdef __HASH_3 + m_Hash2Descendants(0), + #endif + m_Nodes(0), + m_TmpBacks(0) +{ +} + +CPatricia::~CPatricia() +{ + FreeMemory(); +} + +void CPatricia::FreeMemory() +{ + MyFree(m_TmpBacks); + m_TmpBacks = 0; + + ::BigFree(m_Nodes); + m_Nodes = 0; + + ::BigFree(m_HashDescendants); + m_HashDescendants = 0; + + #ifdef __HASH_3 + + ::BigFree(m_Hash2Descendants); + m_Hash2Descendants = 0; + + CLZInWindow::Free(); + + #endif +} + +STDMETHODIMP CPatricia::Create(UInt32 historySize, UInt32 keepAddBufferBefore, + UInt32 matchMaxLen, UInt32 keepAddBufferAfter) +{ + FreeMemory(); + int kNumBitsInNumSameBits = sizeof(CSameBitsType) * 8; + if (kNumBitsInNumSameBits < 32 && ((matchMaxLen * MY_BYTE_SIZE) > ((UInt32)1 << kNumBitsInNumSameBits))) + return E_INVALIDARG; + + const UInt32 kAlignMask = (1 << 16) - 1; + UInt32 windowReservSize = historySize; + windowReservSize += kAlignMask; + windowReservSize &= ~(kAlignMask); + + const UInt32 kMinReservSize = (1 << 19); + if (windowReservSize < kMinReservSize) + windowReservSize = kMinReservSize; + windowReservSize += 256; + + if (!CLZInWindow::Create(historySize + keepAddBufferBefore, + matchMaxLen + keepAddBufferAfter, windowReservSize)) + return E_OUTOFMEMORY; + + _sizeHistory = historySize; + _matchMaxLen = matchMaxLen; + m_HashDescendants = (CDescendant *)BigAlloc(kHashSize * sizeof(CDescendant)); + if (m_HashDescendants == 0) + { + FreeMemory(); + return E_OUTOFMEMORY; + } + + #ifdef __HASH_3 + m_Hash2Descendants = (CDescendant *)BigAlloc(kHash2Size * sizeof(CDescendant)); + if (m_Hash2Descendants == 0) + { + FreeMemory(); + return E_OUTOFMEMORY; + } + #endif + + #ifdef __AUTO_REMOVE + + #ifdef __HASH_3 + m_NumNodes = historySize + _sizeHistory * 4 / 8 + (1 << 19); + #else + m_NumNodes = historySize + _sizeHistory * 4 / 8 + (1 << 10); + #endif + + #else + + UInt32 m_NumNodes = historySize; + + #endif + + const UInt32 kMaxNumNodes = UInt32(1) << (sizeof(CIndex) * 8 - 1); + if (m_NumNodes + 32 > kMaxNumNodes) + return E_INVALIDARG; + + // m_Nodes = (CNode *)::BigAlloc((m_NumNodes + 2) * sizeof(CNode)); + m_Nodes = (CNode *)::BigAlloc((m_NumNodes + 12) * sizeof(CNode)); + if (m_Nodes == 0) + { + FreeMemory(); + return E_OUTOFMEMORY; + } + + m_TmpBacks = (UInt32 *)MyAlloc((_matchMaxLen + 1) * sizeof(UInt32)); + if (m_TmpBacks == 0) + { + FreeMemory(); + return E_OUTOFMEMORY; + } + return S_OK; +} + +STDMETHODIMP CPatricia::Init(ISequentialInStream *aStream) +{ + RINOK(CLZInWindow::Init(aStream)); + + // memset(m_HashDescendants, 0xFF, kHashSize * sizeof(m_HashDescendants[0])); + + #ifdef __HASH_3 + for (UInt32 i = 0; i < kHash2Size; i++) + m_Hash2Descendants[i].MatchPointer = kDescendantsNotInitilized2; + #else + for (UInt32 i = 0; i < kHashSize; i++) + m_HashDescendants[i].MakeEmpty(); + #endif + + m_Nodes[0].NextFreeNode = 1; + m_FreeNode = 0; + m_FreeNodeMax = 0; + #ifdef __AUTO_REMOVE + m_NumUsedNodes = 0; + #else + m_SpecialRemoveMode = false; + #endif + m_SpecialMode = false; + return S_OK; +} + +STDMETHODIMP_(void) CPatricia::ReleaseStream() +{ + // CLZInWindow::ReleaseStream(); +} + +// pos = _pos + kNumHashBytes +// fullCurrentLimit = currentLimit + kNumHashBytes +// fullMatchLen = matchLen + kNumHashBytes + +void CPatricia::ChangeLastMatch(UInt32 hashValue) +{ + UInt32 pos = _pos + kNumHashBytes - 1; + UInt32 descendantIndex; + const Byte *currentBytePointer = _buffer + pos; + UInt32 numLoadedBits = 0; + Byte curByte = 0; // = 0 to disable warning of GCC + CNodePointer node = &m_Nodes[m_HashDescendants[hashValue].NodePointer]; + + while(true) + { + UInt32 numSameBits = node->NumSameBits; + if(numSameBits > 0) + { + if (numLoadedBits < numSameBits) + { + numSameBits -= numLoadedBits; + currentBytePointer += (numSameBits / MY_BYTE_SIZE); + numSameBits %= MY_BYTE_SIZE; + curByte = *currentBytePointer++; + numLoadedBits = MY_BYTE_SIZE; + } + curByte >>= numSameBits; + numLoadedBits -= numSameBits; + } + if(numLoadedBits == 0) + { + curByte = *currentBytePointer++; + numLoadedBits = MY_BYTE_SIZE; + } + descendantIndex = (curByte & kSubNodesMask); + node->LastMatch = pos; + numLoadedBits -= kNumSubBits; + curByte >>= kNumSubBits; + if(node->Descendants[descendantIndex].IsNode()) + node = &m_Nodes[node->Descendants[descendantIndex].NodePointer]; + else + break; + } + node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue; +} + +UInt32 CPatricia::GetLongestMatch(UInt32 *distances) +{ + UInt32 fullCurrentLimit; + if (_pos + _matchMaxLen <= _streamPos) + fullCurrentLimit = _matchMaxLen; + else + { + fullCurrentLimit = _streamPos - _pos; + if(fullCurrentLimit < kNumHashBytes) + return 0; + } + UInt32 pos = _pos + kNumHashBytes; + + #ifdef __HASH_3 + UInt32 hash2Value = ((UInt32(_buffer[_pos])) << 8) | _buffer[_pos + 1]; + UInt32 hashValue = (hash2Value << 8) | _buffer[_pos + 2]; + CDescendant &hash2Descendant = m_Hash2Descendants[hash2Value]; + CDescendant &hashDescendant = m_HashDescendants[hashValue]; + if(hash2Descendant.MatchPointer <= kDescendantEmptyValue2) + { + if(hash2Descendant.MatchPointer == kDescendantsNotInitilized2) + { + UInt32 base = hashValue & 0xFFFF00; + for (UInt32 i = 0; i < 0x100; i++) + m_HashDescendants[base + i].MakeEmpty(); + } + hash2Descendant.MatchPointer = pos + kMatchStartValue2; + hashDescendant.MatchPointer = pos + kMatchStartValue; + return 0; + } + + distances[kNumHash2Bytes] = pos - (hash2Descendant.MatchPointer - kMatchStartValue2) - 1; + hash2Descendant.MatchPointer = pos + kMatchStartValue2; + #ifdef __AUTO_REMOVE + if (distances[kNumHash2Bytes] >= _sizeHistory) + { + if (hashDescendant.IsNode()) + RemoveNode(hashDescendant.NodePointer); + hashDescendant.MatchPointer = pos + kMatchStartValue; + return 0; + } + #endif + if (fullCurrentLimit == kNumHash2Bytes) + return kNumHash2Bytes; + + #else + UInt32 hashValue = UInt32(GetIndexByte(1)) | (UInt32(GetIndexByte(0)) << 8); + CDescendant &hashDescendant = m_HashDescendants[hashValue]; + #endif + + + if(m_SpecialMode) + { + if(hashDescendant.IsMatch()) + m_NumNotChangedCycles = 0; + if(m_NumNotChangedCycles >= _sizeHistory - 1) + { + ChangeLastMatch(hashValue); + m_NumNotChangedCycles = 0; + } + if(GetIndexByte(fullCurrentLimit - 1) == GetIndexByte(fullCurrentLimit - 2)) + { + if(hashDescendant.IsMatch()) + hashDescendant.MatchPointer = pos + kMatchStartValue; + else + m_NumNotChangedCycles++; + for(UInt32 i = kNumHashBytes; i <= fullCurrentLimit; i++) + distances[i] = 0; + return fullCurrentLimit; + } + else if(m_NumNotChangedCycles > 0) + ChangeLastMatch(hashValue); + m_SpecialMode = false; + } + + if(hashDescendant.IsEmpty()) + { + hashDescendant.MatchPointer = pos + kMatchStartValue; + return kPrevHashSize; + } + + UInt32 currentLimit = fullCurrentLimit - kNumHashBytes; + + if(hashDescendant.IsMatch()) + { + CMatchPointer matchPointer = hashDescendant.MatchPointer; + UInt32 backReal = pos - (matchPointer - kMatchStartValue); + UInt32 back = backReal - 1; + #ifdef __AUTO_REMOVE + if (back >= _sizeHistory) + { + hashDescendant.MatchPointer = pos + kMatchStartValue; + return kPrevHashSize; + } + #endif + + UInt32 matchLen; + distances += kNumHashBytes; + Byte *buffer = _buffer + pos; + for(matchLen = 0; true; matchLen++) + { + *distances++ = back; + if (matchLen == currentLimit) + { + hashDescendant.MatchPointer = pos + kMatchStartValue; + return kNumHashBytes + matchLen; + } + if (buffer[matchLen] != buffer[(size_t)matchLen - backReal]) + break; + } + + // UInt32 matchLen = GetMatchLen(kNumHashBytes, back, currentLimit); + + UInt32 fullMatchLen = matchLen + kNumHashBytes; + hashDescendant.NodePointer = m_FreeNode; + CNodePointer node = &m_Nodes[m_FreeNode]; + m_FreeNode = node->NextFreeNode; + #ifdef __AUTO_REMOVE + m_NumUsedNodes++; + #endif + if (m_FreeNode > m_FreeNodeMax) + { + m_FreeNodeMax = m_FreeNode; + m_Nodes[m_FreeNode].NextFreeNode = m_FreeNode + 1; + } + + for (UInt32 i = 0; i < kNumSubNodes; i++) + node->Descendants[i].NodePointer = kDescendantEmptyValue; + node->LastMatch = pos; + + Byte byteNew = GetIndexByte(fullMatchLen); + Byte byteOld = GetIndexByte(fullMatchLen - backReal); + Byte bitsNew, bitsOld; + UInt32 numSameBits = matchLen * MY_BYTE_SIZE; + while (true) + { + bitsNew = (byteNew & kSubNodesMask); + bitsOld = (byteOld & kSubNodesMask); + if(bitsNew != bitsOld) + break; + byteNew >>= kNumSubBits; + byteOld >>= kNumSubBits; + numSameBits += kNumSubBits; + } + node->NumSameBits = CSameBitsType(numSameBits); + node->Descendants[bitsNew].MatchPointer = pos + kMatchStartValue; + node->Descendants[bitsOld].MatchPointer = matchPointer; + return fullMatchLen; + } + const Byte *baseCurrentBytePointer = _buffer + pos; + const Byte *currentBytePointer = baseCurrentBytePointer; + UInt32 numLoadedBits = 0; + Byte curByte = 0; + CIndex *nodePointerPointer = &hashDescendant.NodePointer; + CNodePointer node = &m_Nodes[*nodePointerPointer]; + distances += kNumHashBytes; + const Byte *bytePointerLimit = baseCurrentBytePointer + currentLimit; + const Byte *currentAddingOffset = _buffer; + + #ifdef __AUTO_REMOVE + UInt32 lowPos; + if (pos > _sizeHistory) + lowPos = pos - _sizeHistory; + else + lowPos = 0; + #endif + + while(true) + { + #ifdef __AUTO_REMOVE + if (node->LastMatch < lowPos) + { + RemoveNode(*nodePointerPointer); + *nodePointerPointer = pos + kMatchStartValue; + if (currentBytePointer == baseCurrentBytePointer) + return kPrevHashSize; + return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1); + } + #endif + if(numLoadedBits == 0) + { + *distances++ = pos - node->LastMatch - 1; + if(currentBytePointer >= bytePointerLimit) + { + for (UInt32 i = 0; i < kNumSubNodes; i++) + node->Descendants[i].MatchPointer = pos + kMatchStartValue; + node->LastMatch = pos; + node->NumSameBits = 0; + return fullCurrentLimit; + } + curByte = (*currentBytePointer++); + currentAddingOffset++; + numLoadedBits = MY_BYTE_SIZE; + } + UInt32 numSameBits = node->NumSameBits; + if(numSameBits > 0) + { + Byte byteXOR = ((*(currentAddingOffset + node->LastMatch -1)) >> + (MY_BYTE_SIZE - numLoadedBits)) ^ curByte; + while(numLoadedBits <= numSameBits) + { + if(byteXOR != 0) + { + AddInternalNode(node, nodePointerPointer, curByte, byteXOR, + numSameBits, pos); + return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1); + } + *distances++ = pos - node->LastMatch - 1; + numSameBits -= numLoadedBits; + if(currentBytePointer >= bytePointerLimit) + { + for (UInt32 i = 0; i < kNumSubNodes; i++) + node->Descendants[i].MatchPointer = pos + kMatchStartValue; + node->LastMatch = pos; + node->NumSameBits = CSameBitsType(node->NumSameBits - numSameBits); + return fullCurrentLimit; + } + numLoadedBits = MY_BYTE_SIZE; + curByte = (*currentBytePointer++); + byteXOR = curByte ^ (*(currentAddingOffset + node->LastMatch)); + currentAddingOffset++; + } + if((byteXOR & ((1 << numSameBits) - 1)) != 0) + { + AddInternalNode(node, nodePointerPointer, curByte, byteXOR, + numSameBits, pos); + return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1); + } + curByte >>= numSameBits; + numLoadedBits -= numSameBits; + } + UInt32 descendantIndex = (curByte & kSubNodesMask); + numLoadedBits -= kNumSubBits; + nodePointerPointer = &node->Descendants[descendantIndex].NodePointer; + UInt32 nextNodeIndex = *nodePointerPointer; + node->LastMatch = pos; + if (nextNodeIndex < kDescendantEmptyValue) + { + curByte >>= kNumSubBits; + node = &m_Nodes[nextNodeIndex]; + } + else if (nextNodeIndex == kDescendantEmptyValue) + { + node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue; + return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1); + } + else + break; + } + + UInt32 descendantIndex = (curByte & kSubNodesMask); + curByte >>= kNumSubBits; + CMatchPointer matchPointer = node->Descendants[descendantIndex].MatchPointer; + CMatchPointer realMatchPointer; + realMatchPointer = matchPointer - kMatchStartValue; + + #ifdef __AUTO_REMOVE + if (realMatchPointer < lowPos) + { + node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue; + return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1); + } + #endif + + Byte byteXOR; + UInt32 numSameBits = 0; + if(numLoadedBits != 0) + { + Byte matchByte = *(currentAddingOffset + realMatchPointer -1); + matchByte >>= (MY_BYTE_SIZE - numLoadedBits); + byteXOR = matchByte ^ curByte; + if(byteXOR != 0) + { + AddLeafNode(node, curByte, byteXOR, numSameBits, pos, descendantIndex); + return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1); + } + numSameBits += numLoadedBits; + } + + const Byte *matchBytePointer = _buffer + realMatchPointer + + (currentBytePointer - baseCurrentBytePointer); + for(; currentBytePointer < bytePointerLimit; numSameBits += MY_BYTE_SIZE) + { + curByte = (*currentBytePointer++); + *distances++ = pos - realMatchPointer - 1; + byteXOR = curByte ^ (*matchBytePointer++); + if(byteXOR != 0) + { + AddLeafNode(node, curByte, byteXOR, numSameBits, pos, descendantIndex); + return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1); + } + } + *distances = pos - realMatchPointer - 1; + node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue; + + if(*distances == 0) + { + m_SpecialMode = true; + m_NumNotChangedCycles = 0; + } + return fullCurrentLimit; +} + +STDMETHODIMP_(void) CPatricia::DummyLongestMatch() +{ + GetLongestMatch(m_TmpBacks); +} + + +// ------------------------------------ +// Remove Match + +typedef Byte CRemoveDataWord; + +static const int kSizeRemoveDataWordInBits = MY_BYTE_SIZE * sizeof(CRemoveDataWord); + +#ifndef __AUTO_REMOVE + +void CPatricia::RemoveMatch() +{ + if(m_SpecialRemoveMode) + { + if(GetIndexByte(_matchMaxLen - 1 - _sizeHistory) == + GetIndexByte(_matchMaxLen - _sizeHistory)) + return; + m_SpecialRemoveMode = false; + } + UInt32 pos = _pos + kNumHashBytes - _sizeHistory; + + #ifdef __HASH_3 + const Byte *pp = _buffer + _pos - _sizeHistory; + UInt32 hash2Value = ((UInt32(pp[0])) << 8) | pp[1]; + UInt32 hashValue = (hash2Value << 8) | pp[2]; + CDescendant &hashDescendant = m_HashDescendants[hashValue]; + CDescendant &hash2Descendant = m_Hash2Descendants[hash2Value]; + if (hash2Descendant >= kMatchStartValue2) + if(hash2Descendant.MatchPointer == pos + kMatchStartValue2) + hash2Descendant.MatchPointer = kDescendantEmptyValue2; + #else + UInt32 hashValue = UInt32(GetIndexByte(1 - _sizeHistory)) | + (UInt32(GetIndexByte(0 - _sizeHistory)) << 8); + CDescendant &hashDescendant = m_HashDescendants[hashValue]; + #endif + + if(hashDescendant.IsEmpty()) + return; + if(hashDescendant.IsMatch()) + { + if(hashDescendant.MatchPointer == pos + kMatchStartValue) + hashDescendant.MakeEmpty(); + return; + } + + UInt32 descendantIndex; + const CRemoveDataWord *currentPointer = (const CRemoveDataWord *)(_buffer + pos); + UInt32 numLoadedBits = 0; + CRemoveDataWord curWord = 0; // = 0 to disable GCC warning + + CIndex *nodePointerPointer = &hashDescendant.NodePointer; + + CNodePointer node = &m_Nodes[hashDescendant.NodePointer]; + + while(true) + { + if(numLoadedBits == 0) + { + curWord = *currentPointer++; + numLoadedBits = kSizeRemoveDataWordInBits; + } + UInt32 numSameBits = node->NumSameBits; + if(numSameBits > 0) + { + if (numLoadedBits <= numSameBits) + { + numSameBits -= numLoadedBits; + currentPointer += (numSameBits / kSizeRemoveDataWordInBits); + numSameBits %= kSizeRemoveDataWordInBits; + curWord = *currentPointer++; + numLoadedBits = kSizeRemoveDataWordInBits; + } + curWord >>= numSameBits; + numLoadedBits -= numSameBits; + } + descendantIndex = (curWord & kSubNodesMask); + numLoadedBits -= kNumSubBits; + curWord >>= kNumSubBits; + UInt32 nextNodeIndex = node->Descendants[descendantIndex].NodePointer; + if (nextNodeIndex < kDescendantEmptyValue) + { + nodePointerPointer = &node->Descendants[descendantIndex].NodePointer; + node = &m_Nodes[nextNodeIndex]; + } + else + break; + } + if (node->Descendants[descendantIndex].MatchPointer != pos + kMatchStartValue) + { + const Byte *currentBytePointer = _buffer + _pos - _sizeHistory; + const Byte *currentBytePointerLimit = currentBytePointer + _matchMaxLen; + for(;currentBytePointer < currentBytePointerLimit; currentBytePointer++) + if(*currentBytePointer != *(currentBytePointer+1)) + return; + m_SpecialRemoveMode = true; + return; + } + + UInt32 numNodes = 0, numMatches = 0; + + UInt32 i; + for (i = 0; i < kNumSubNodes; i++) + { + UInt32 nodeIndex = node->Descendants[i].NodePointer; + if (nodeIndex < kDescendantEmptyValue) + numNodes++; + else if (nodeIndex > kDescendantEmptyValue) + numMatches++; + } + numMatches -= 1; + if (numNodes + numMatches > 1) + { + node->Descendants[descendantIndex].MakeEmpty(); + return; + } + if(numNodes == 1) + { + UInt32 i; + for (i = 0; i < kNumSubNodes; i++) + if (node->Descendants[i].IsNode()) + break; + UInt32 nextNodeIndex = node->Descendants[i].NodePointer; + CNodePointer nextNode = &m_Nodes[nextNodeIndex]; + nextNode->NumSameBits += node->NumSameBits + kNumSubBits; + *node = *nextNode; + + nextNode->NextFreeNode = m_FreeNode; + m_FreeNode = nextNodeIndex; + return; + } + UInt32 matchPointer = 0; // = 0 to disable GCC warning + for (i = 0; i < kNumSubNodes; i++) + if (node->Descendants[i].IsMatch() && i != descendantIndex) + { + matchPointer = node->Descendants[i].MatchPointer; + break; + } + node->NextFreeNode = m_FreeNode; + m_FreeNode = *nodePointerPointer; + *nodePointerPointer = matchPointer; +} +#endif + + +// Commented code is more correct, but it gives warning +// on GCC: (1 << 32) +// So we use kMatchStartValue twice: +// kMatchStartValue = UInt32(1) << (kNumBitsInIndex - 1); +// must be defined in Pat.h +/* +const UInt32 kNormalizeStartPos = (UInt32(1) << (kNumBitsInIndex)) - + kMatchStartValue - kNumHashBytes - 1; +*/ +const UInt32 kNormalizeStartPos = kMatchStartValue - kNumHashBytes - 1; + +STDMETHODIMP CPatricia::MovePos() +{ + #ifndef __AUTO_REMOVE + if(_pos >= _sizeHistory) + RemoveMatch(); + #endif + RINOK(CLZInWindow::MovePos()); + #ifdef __AUTO_REMOVE + if (m_NumUsedNodes >= m_NumNodes) + TestRemoveNodes(); + #endif + if (_pos >= kNormalizeStartPos) + { + #ifdef __AUTO_REMOVE + TestRemoveNodesAndNormalize(); + #else + Normalize(); + #endif + } + return S_OK; +} + +#ifndef __AUTO_REMOVE + +void CPatricia::NormalizeDescendant(CDescendant &descendant, UInt32 subValue) +{ + if (descendant.IsEmpty()) + return; + if (descendant.IsMatch()) + descendant.MatchPointer = descendant.MatchPointer - subValue; + else + { + CNode &node = m_Nodes[descendant.NodePointer]; + node.LastMatch = node.LastMatch - subValue; + for (UInt32 i = 0; i < kNumSubNodes; i++) + NormalizeDescendant(node.Descendants[i], subValue); + } +} + +void CPatricia::Normalize() +{ + UInt32 subValue = _pos - _sizeHistory; + CLZInWindow::ReduceOffsets(subValue); + + #ifdef __HASH_3 + + for(UInt32 hash = 0; hash < kHash2Size; hash++) + { + CDescendant &descendant = m_Hash2Descendants[hash]; + if (descendant.MatchPointer != kDescendantsNotInitilized2) + { + UInt32 base = hash << 8; + for (UInt32 i = 0; i < 0x100; i++) + NormalizeDescendant(m_HashDescendants[base + i], subValue); + } + if (descendant.MatchPointer < kMatchStartValue2) + continue; + descendant.MatchPointer = descendant.MatchPointer - subValue; + } + + #else + + for(UInt32 hash = 0; hash < kHashSize; hash++) + NormalizeDescendant(m_HashDescendants[hash], subValue); + + #endif + +} + +#else + +void CPatricia::TestRemoveDescendant(CDescendant &descendant, UInt32 limitPos) +{ + CNode &node = m_Nodes[descendant.NodePointer]; + UInt32 numChilds = 0; + UInt32 childIndex = 0; // = 0 to disable GCC warning + for (UInt32 i = 0; i < kNumSubNodes; i++) + { + CDescendant &descendant2 = node.Descendants[i]; + if (descendant2.IsEmpty()) + continue; + if (descendant2.IsMatch()) + { + if (descendant2.MatchPointer < limitPos) + descendant2.MakeEmpty(); + else + { + numChilds++; + childIndex = i; + } + } + else + { + TestRemoveDescendant(descendant2, limitPos); + if (!descendant2.IsEmpty()) + { + numChilds++; + childIndex = i; + } + } + } + if (numChilds > 1) + return; + + CIndex nodePointerTemp = descendant.NodePointer; + if (numChilds == 1) + { + const CDescendant &descendant2 = node.Descendants[childIndex]; + if (descendant2.IsNode()) + m_Nodes[descendant2.NodePointer].NumSameBits += node.NumSameBits + kNumSubBits; + descendant = descendant2; + } + else + descendant.MakeEmpty(); + node.NextFreeNode = m_FreeNode; + m_FreeNode = nodePointerTemp; + m_NumUsedNodes--; +} + +void CPatricia::RemoveNode(UInt32 index) +{ + CNode &node = m_Nodes[index]; + for (UInt32 i = 0; i < kNumSubNodes; i++) + { + CDescendant &descendant2 = node.Descendants[i]; + if (descendant2.IsNode()) + RemoveNode(descendant2.NodePointer); + } + node.NextFreeNode = m_FreeNode; + m_FreeNode = index; + m_NumUsedNodes--; +} + +void CPatricia::TestRemoveNodes() +{ + UInt32 limitPos = kMatchStartValue + _pos - _sizeHistory + kNumHashBytes; + + #ifdef __HASH_3 + + UInt32 limitPos2 = kMatchStartValue2 + _pos - _sizeHistory + kNumHashBytes; + for(UInt32 hash = 0; hash < kHash2Size; hash++) + { + CDescendant &descendant = m_Hash2Descendants[hash]; + if (descendant.MatchPointer != kDescendantsNotInitilized2) + { + UInt32 base = hash << 8; + for (UInt32 i = 0; i < 0x100; i++) + { + CDescendant &descendant = m_HashDescendants[base + i]; + if (descendant.IsEmpty()) + continue; + if (descendant.IsMatch()) + { + if (descendant.MatchPointer < limitPos) + descendant.MakeEmpty(); + } + else + TestRemoveDescendant(descendant, limitPos); + } + } + if (descendant.MatchPointer < kMatchStartValue2) + continue; + if (descendant.MatchPointer < limitPos2) + descendant.MatchPointer = kDescendantEmptyValue2; + } + + #else + + for(UInt32 hash = 0; hash < kHashSize; hash++) + { + CDescendant &descendant = m_HashDescendants[hash]; + if (descendant.IsEmpty()) + continue; + if (descendant.IsMatch()) + { + if (descendant.MatchPointer < limitPos) + descendant.MakeEmpty(); + } + else + TestRemoveDescendant(descendant, limitPos); + } + + #endif +} + +void CPatricia::TestRemoveAndNormalizeDescendant(CDescendant &descendant, + UInt32 limitPos, UInt32 subValue) +{ + if (descendant.IsEmpty()) + return; + if (descendant.IsMatch()) + { + if (descendant.MatchPointer < limitPos) + descendant.MakeEmpty(); + else + descendant.MatchPointer = descendant.MatchPointer - subValue; + return; + } + CNode &node = m_Nodes[descendant.NodePointer]; + UInt32 numChilds = 0; + UInt32 childIndex = 0; // = 0 to disable GCC warning + for (UInt32 i = 0; i < kNumSubNodes; i++) + { + CDescendant &descendant2 = node.Descendants[i]; + TestRemoveAndNormalizeDescendant(descendant2, limitPos, subValue); + if (!descendant2.IsEmpty()) + { + numChilds++; + childIndex = i; + } + } + if (numChilds > 1) + { + node.LastMatch = node.LastMatch - subValue; + return; + } + + CIndex nodePointerTemp = descendant.NodePointer; + if (numChilds == 1) + { + const CDescendant &descendant2 = node.Descendants[childIndex]; + if (descendant2.IsNode()) + m_Nodes[descendant2.NodePointer].NumSameBits += node.NumSameBits + kNumSubBits; + descendant = descendant2; + } + else + descendant.MakeEmpty(); + node.NextFreeNode = m_FreeNode; + m_FreeNode = nodePointerTemp; + m_NumUsedNodes--; +} + +void CPatricia::TestRemoveNodesAndNormalize() +{ + UInt32 subValue = _pos - _sizeHistory; + UInt32 limitPos = kMatchStartValue + _pos - _sizeHistory + kNumHashBytes; + CLZInWindow::ReduceOffsets(subValue); + + #ifdef __HASH_3 + + UInt32 limitPos2 = kMatchStartValue2 + _pos - _sizeHistory + kNumHashBytes; + for(UInt32 hash = 0; hash < kHash2Size; hash++) + { + CDescendant &descendant = m_Hash2Descendants[hash]; + if (descendant.MatchPointer != kDescendantsNotInitilized2) + { + UInt32 base = hash << 8; + for (UInt32 i = 0; i < 0x100; i++) + TestRemoveAndNormalizeDescendant(m_HashDescendants[base + i], limitPos, subValue); + } + if (descendant.MatchPointer < kMatchStartValue2) + continue; + if (descendant.MatchPointer < limitPos2) + descendant.MatchPointer = kDescendantEmptyValue2; + else + descendant.MatchPointer = descendant.MatchPointer - subValue; + } + + #else + + for(UInt32 hash = 0; hash < kHashSize; hash++) + TestRemoveAndNormalizeDescendant(m_HashDescendants[hash], limitPos, subValue); + + #endif +} + +#endif + +STDMETHODIMP_(Byte) CPatricia::GetIndexByte(Int32 index) +{ + return CLZInWindow::GetIndexByte(index); +} + +STDMETHODIMP_(UInt32) CPatricia::GetMatchLen(Int32 index, UInt32 back, UInt32 limit) +{ + return CLZInWindow::GetMatchLen(index, back, limit); +} + +STDMETHODIMP_(UInt32) CPatricia::GetNumAvailableBytes() +{ + return CLZInWindow::GetNumAvailableBytes(); +} + +STDMETHODIMP_(const Byte *) CPatricia::GetPointerToCurrentPos() +{ + return CLZInWindow::GetPointerToCurrentPos(); +} + +} diff --git a/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/StdAfx.h b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/StdAfx.h new file mode 100644 index 00000000..3de038a4 --- /dev/null +++ b/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/StdAfx.h @@ -0,0 +1,6 @@ +// StdAfx.h + +#ifndef __STDAFX_H +#define __STDAFX_H + +#endif -- cgit v1.2.3-54-g00ecf