summaryrefslogtreecommitdiff
path: root/release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat.h
diff options
context:
space:
mode:
Diffstat (limited to 'release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat.h')
-rw-r--r--release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat.h318
1 files changed, 318 insertions, 0 deletions
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