Annotation of elwix/tools/oldlzma/SRC/7zip/Compress/LZ/Patricia/Pat.h, revision 1.1
1.1 ! misho 1: // Pat.h
! 2:
! 3: // #ifndef __PATRICIA__H
! 4: // #define __PATRICIA__H
! 5:
! 6: #include "../../../../Common/MyCom.h"
! 7: #include "../../../../Common/Types.h"
! 8: #include "../LZInWindow.h"
! 9:
! 10: namespace PAT_NAMESPACE {
! 11:
! 12: struct CNode;
! 13:
! 14: typedef CNode *CNodePointer;
! 15:
! 16: // #define __AUTO_REMOVE
! 17:
! 18: // #define __NODE_4_BITS
! 19: // #define __NODE_3_BITS
! 20: // #define __NODE_2_BITS
! 21: // #define __NODE_2_BITS_PADDING
! 22:
! 23: // #define __HASH_3
! 24:
! 25:
! 26: typedef UInt32 CIndex;
! 27:
! 28: #ifdef __NODE_4_BITS
! 29: typedef UInt32 CIndex2;
! 30: typedef UInt32 CSameBitsType;
! 31: #else
! 32: #ifdef __NODE_3_BITS
! 33: typedef UInt32 CIndex2;
! 34: typedef UInt32 CSameBitsType;
! 35: #else
! 36:
! 37: typedef UInt32 CIndex;
! 38: typedef UInt32 CSameBitsType;
! 39:
! 40: typedef CIndex CIndex2;
! 41: #endif
! 42: #endif
! 43:
! 44: const UInt32 kNumBitsInIndex = sizeof(CIndex) * 8;
! 45: const UInt32 kMatchStartValue = UInt32(1) << (kNumBitsInIndex - 1);
! 46: // don't change kMatchStartValue definition, since it is used in
! 47: // PatMain.h:
! 48:
! 49: typedef CIndex CMatchPointer;
! 50:
! 51: const UInt32 kDescendantEmptyValue = kMatchStartValue - 1;
! 52:
! 53: union CDescendant
! 54: {
! 55: CIndex NodePointer;
! 56: CMatchPointer MatchPointer;
! 57: bool IsEmpty() const { return NodePointer == kDescendantEmptyValue; }
! 58: bool IsNode() const { return NodePointer < kDescendantEmptyValue; }
! 59: bool IsMatch() const { return NodePointer > kDescendantEmptyValue; }
! 60: void MakeEmpty() { NodePointer = kDescendantEmptyValue; }
! 61: };
! 62:
! 63: #undef MY_BYTE_SIZE
! 64:
! 65: #ifdef __NODE_4_BITS
! 66: #define MY_BYTE_SIZE 8
! 67: const UInt32 kNumSubBits = 4;
! 68: #else
! 69: #ifdef __NODE_3_BITS
! 70: #define MY_BYTE_SIZE 9
! 71: const UInt32 kNumSubBits = 3;
! 72: #else
! 73: #define MY_BYTE_SIZE 8
! 74: #ifdef __NODE_2_BITS
! 75: const UInt32 kNumSubBits = 2;
! 76: #else
! 77: const UInt32 kNumSubBits = 1;
! 78: #endif
! 79: #endif
! 80: #endif
! 81:
! 82: const UInt32 kNumSubNodes = 1 << kNumSubBits;
! 83: const UInt32 kSubNodesMask = kNumSubNodes - 1;
! 84:
! 85: struct CNode
! 86: {
! 87: CIndex2 LastMatch;
! 88: CSameBitsType NumSameBits;
! 89: union
! 90: {
! 91: CDescendant Descendants[kNumSubNodes];
! 92: UInt32 NextFreeNode;
! 93: };
! 94: #ifdef __NODE_2_BITS
! 95: #ifdef __NODE_2_BITS_PADDING
! 96: UInt32 Padding[2];
! 97: #endif
! 98: #endif
! 99: };
! 100:
! 101: #undef kIDNumBitsByte
! 102: #undef kIDNumBitsString
! 103:
! 104: #ifdef __NODE_4_BITS
! 105: #define kIDNumBitsByte 0x30
! 106: #define kIDNumBitsString TEXT("4")
! 107: #else
! 108: #ifdef __NODE_3_BITS
! 109: #define kIDNumBitsByte 0x20
! 110: #define kIDNumBitsString TEXT("3")
! 111: #else
! 112: #ifdef __NODE_2_BITS
! 113: #define kIDNumBitsByte 0x10
! 114: #define kIDNumBitsString TEXT("2")
! 115: #else
! 116: #define kIDNumBitsByte 0x00
! 117: #define kIDNumBitsString TEXT("1")
! 118: #endif
! 119: #endif
! 120: #endif
! 121:
! 122: #undef kIDManualRemoveByte
! 123: #undef kIDManualRemoveString
! 124:
! 125: #ifdef __AUTO_REMOVE
! 126: #define kIDManualRemoveByte 0x00
! 127: #define kIDManualRemoveString TEXT("")
! 128: #else
! 129: #define kIDManualRemoveByte 0x08
! 130: #define kIDManualRemoveString TEXT("R")
! 131: #endif
! 132:
! 133: #undef kIDHash3Byte
! 134: #undef kIDHash3String
! 135:
! 136: #ifdef __HASH_3
! 137: #define kIDHash3Byte 0x04
! 138: #define kIDHash3String TEXT("H")
! 139: #else
! 140: #define kIDHash3Byte 0x00
! 141: #define kIDHash3String TEXT("")
! 142: #endif
! 143:
! 144: #undef kIDUse3BytesByte
! 145: #undef kIDUse3BytesString
! 146:
! 147: #define kIDUse3BytesByte 0x00
! 148: #define kIDUse3BytesString TEXT("")
! 149:
! 150: #undef kIDPaddingByte
! 151: #undef kIDPaddingString
! 152:
! 153: #ifdef __NODE_2_BITS_PADDING
! 154: #define kIDPaddingByte 0x01
! 155: #define kIDPaddingString TEXT("P")
! 156: #else
! 157: #define kIDPaddingByte 0x00
! 158: #define kIDPaddingString TEXT("")
! 159: #endif
! 160:
! 161:
! 162: // #undef kIDString
! 163: // #define kIDString TEXT("Compress.MatchFinderPat") kIDNumBitsString kIDManualRemoveString kIDUse3BytesString kIDPaddingString kIDHash3String
! 164:
! 165: // {23170F69-40C1-278C-01XX-0000000000}
! 166:
! 167: DEFINE_GUID(PAT_CLSID,
! 168: 0x23170F69, 0x40C1, 0x278C, 0x01,
! 169: kIDNumBitsByte |
! 170: kIDManualRemoveByte | kIDHash3Byte | kIDUse3BytesByte | kIDPaddingByte,
! 171: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00);
! 172:
! 173: // III(PAT_NAMESPACE)
! 174:
! 175: class CPatricia:
! 176: public IMatchFinder,
! 177: public IMatchFinderSetCallback,
! 178: public CMyUnknownImp,
! 179: CLZInWindow
! 180: {
! 181: MY_UNKNOWN_IMP1(IMatchFinderSetCallback)
! 182:
! 183: STDMETHOD(Init)(ISequentialInStream *aStream);
! 184: STDMETHOD_(void, ReleaseStream)();
! 185: STDMETHOD(MovePos)();
! 186: STDMETHOD_(Byte, GetIndexByte)(Int32 index);
! 187: STDMETHOD_(UInt32, GetMatchLen)(Int32 index, UInt32 back, UInt32 limit);
! 188: STDMETHOD_(UInt32, GetNumAvailableBytes)();
! 189: STDMETHOD(Create)(UInt32 historySize,
! 190: UInt32 keepAddBufferBefore, UInt32 matchMaxLen,
! 191: UInt32 keepAddBufferAfter);
! 192: STDMETHOD_(UInt32, GetLongestMatch)(UInt32 *distances);
! 193: STDMETHOD_(void, DummyLongestMatch)();
! 194: STDMETHOD_(const Byte *, GetPointerToCurrentPos)();
! 195:
! 196: void FreeMemory();
! 197: public:
! 198: CPatricia();
! 199: ~CPatricia();
! 200:
! 201: UInt32 _sizeHistory;
! 202: UInt32 _matchMaxLen;
! 203:
! 204: CDescendant *m_HashDescendants;
! 205: #ifdef __HASH_3
! 206: CDescendant *m_Hash2Descendants;
! 207: #endif
! 208:
! 209: CNode *m_Nodes;
! 210:
! 211: UInt32 m_FreeNode;
! 212: UInt32 m_FreeNodeMax;
! 213:
! 214: #ifdef __AUTO_REMOVE
! 215: UInt32 m_NumUsedNodes;
! 216: UInt32 m_NumNodes;
! 217: #else
! 218: bool m_SpecialRemoveMode;
! 219: #endif
! 220:
! 221: bool m_SpecialMode;
! 222: UInt32 m_NumNotChangedCycles;
! 223: UInt32 *m_TmpBacks;
! 224:
! 225: CMyComPtr<IMatchFinderCallback> m_Callback;
! 226:
! 227: virtual void BeforeMoveBlock();
! 228: virtual void AfterMoveBlock();
! 229:
! 230: // IMatchFinderSetCallback
! 231: STDMETHOD(SetCallback)(IMatchFinderCallback *callback);
! 232:
! 233: void ChangeLastMatch(UInt32 hashValue);
! 234:
! 235: #ifdef __AUTO_REMOVE
! 236: void TestRemoveDescendant(CDescendant &descendant, UInt32 limitPos);
! 237: void TestRemoveNodes();
! 238: void RemoveNode(UInt32 index);
! 239: void TestRemoveAndNormalizeDescendant(CDescendant &descendant,
! 240: UInt32 limitPos, UInt32 subValue);
! 241: void TestRemoveNodesAndNormalize();
! 242: #else
! 243: void NormalizeDescendant(CDescendant &descendant, UInt32 subValue);
! 244: void Normalize();
! 245: void RemoveMatch();
! 246: #endif
! 247: private:
! 248: void AddInternalNode(CNodePointer aNode, CIndex *aNodePointerPointer,
! 249: Byte aByte, Byte aByteXOR, UInt32 aNumSameBits, UInt32 aPos)
! 250: {
! 251: while((aByteXOR & kSubNodesMask) == 0)
! 252: {
! 253: aByteXOR >>= kNumSubBits;
! 254: aByte >>= kNumSubBits;
! 255: aNumSameBits -= kNumSubBits;
! 256: }
! 257: // Insert New Node
! 258: CNodePointer aNewNode = &m_Nodes[m_FreeNode];
! 259: UInt32 aNodeIndex = *aNodePointerPointer;
! 260: *aNodePointerPointer = m_FreeNode;
! 261: m_FreeNode = aNewNode->NextFreeNode;
! 262: #ifdef __AUTO_REMOVE
! 263: m_NumUsedNodes++;
! 264: #endif
! 265: if (m_FreeNode > m_FreeNodeMax)
! 266: {
! 267: m_FreeNodeMax = m_FreeNode;
! 268: m_Nodes[m_FreeNode].NextFreeNode = m_FreeNode + 1;
! 269: }
! 270:
! 271: UInt32 aBitsNew = aByte & kSubNodesMask;
! 272: UInt32 aBitsOld = (aByte ^ aByteXOR) & kSubNodesMask;
! 273: for (UInt32 i = 0; i < kNumSubNodes; i++)
! 274: aNewNode->Descendants[i].NodePointer = kDescendantEmptyValue;
! 275: aNewNode->Descendants[aBitsNew].MatchPointer = aPos + kMatchStartValue;
! 276: aNewNode->Descendants[aBitsOld].NodePointer = aNodeIndex;
! 277: aNewNode->NumSameBits = CSameBitsType(aNode->NumSameBits - aNumSameBits);
! 278: aNewNode->LastMatch = aPos;
! 279:
! 280: aNode->NumSameBits = CSameBitsType(aNumSameBits - kNumSubBits);
! 281: }
! 282:
! 283: void AddLeafNode(CNodePointer aNode, Byte aByte, Byte aByteXOR,
! 284: UInt32 aNumSameBits, UInt32 aPos, UInt32 aDescendantIndex)
! 285: {
! 286: for(;(aByteXOR & kSubNodesMask) == 0; aNumSameBits += kNumSubBits)
! 287: {
! 288: aByte >>= kNumSubBits;
! 289: aByteXOR >>= kNumSubBits;
! 290: }
! 291: UInt32 aNewNodeIndex = m_FreeNode;
! 292: CNodePointer aNewNode = &m_Nodes[m_FreeNode];
! 293: m_FreeNode = aNewNode->NextFreeNode;
! 294: #ifdef __AUTO_REMOVE
! 295: m_NumUsedNodes++;
! 296: #endif
! 297: if (m_FreeNode > m_FreeNodeMax)
! 298: {
! 299: m_FreeNodeMax = m_FreeNode;
! 300: m_Nodes[m_FreeNode].NextFreeNode = m_FreeNode + 1;
! 301: }
! 302:
! 303: UInt32 aBitsNew = (aByte & kSubNodesMask);
! 304: UInt32 aBitsOld = (aByte ^ aByteXOR) & kSubNodesMask;
! 305: for (UInt32 i = 0; i < kNumSubNodes; i++)
! 306: aNewNode->Descendants[i].NodePointer = kDescendantEmptyValue;
! 307: aNewNode->Descendants[aBitsNew].MatchPointer = aPos + kMatchStartValue;
! 308: aNewNode->Descendants[aBitsOld].MatchPointer =
! 309: aNode->Descendants[aDescendantIndex].MatchPointer;
! 310: aNewNode->NumSameBits = CSameBitsType(aNumSameBits);
! 311: aNewNode->LastMatch = aPos;
! 312: aNode->Descendants[aDescendantIndex].NodePointer = aNewNodeIndex;
! 313: }
! 314: };
! 315:
! 316: }
! 317:
! 318: // #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to Pat.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / elwix / tools / oldlzma / SRC / 7zip / Compress / LZ / Patricia