diff options
Diffstat (limited to 'release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ')
26 files changed, 2813 insertions, 0 deletions
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<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/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<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:
+ 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<IMatchFinderCallback> 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
|