Annotation of elwix/tools/oldlzma/SRC/7zip/Compress/LZ/Patricia/Pat.h, revision 1.1.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