Debian Codegraph @

utils/lzma/SRC/7zip/Compress/LZ/Patricia/Pat.h

raw
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