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/Patricia/Pat.h | 318 +++++++++++++++++++++ 1 file changed, 318 insertions(+) create mode 100644 release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat.h (limited to 'release/src/linux/linux/scripts/squashfs/lzma/C/7zip/Compress/LZ/Patricia/Pat.h') 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 -- cgit v1.2.3-54-g00ecf