Debian Codegraph @

utils/lzma/SRC/7zip/Compress/LZ/HashChain/HCMain.h

raw
1 // HC.h
2
3 #include "../../../../Common/Defs.h"
4 #include "../../../../Common/CRC.h"
5 #include "../../../../Common/Alloc.h"
6
7 namespace HC_NAMESPACE {
8
9 #ifdef HASH_ARRAY_2
10 static const UInt32 kHash2Size = 1 << 10;
11 #ifdef HASH_ARRAY_3
12 static const UInt32 kNumHashDirectBytes = 0;
13 static const UInt32 kNumHashBytes = 4;
14 static const UInt32 kHash3Size = 1 << 18;
15 #ifdef HASH_BIG
16 static const UInt32 kHashSize = 1 << 23;
17 #else
18 static const UInt32 kHashSize = 1 << 20;
19 #endif
20 #else
21 static const UInt32 kNumHashDirectBytes = 0;
22 static const UInt32 kNumHashBytes = 3;
23 static const UInt32 kHashSize = 1 << (16);
24 #endif
25 #else
26 #ifdef HASH_ZIP
27 static const UInt32 kNumHashDirectBytes = 0;
28 static const UInt32 kNumHashBytes = 3;
29 static const UInt32 kHashSize = 1 << 16;
30 #else
31 #define THERE_ARE_DIRECT_HASH_BYTES
32 static const UInt32 kNumHashDirectBytes = 2;
33 static const UInt32 kNumHashBytes = 2;
34 static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
35 #endif
36 #endif
37
38 static const UInt32 kHashSizeSum = kHashSize
39 #ifdef HASH_ARRAY_2
40 + kHash2Size
41 #ifdef HASH_ARRAY_3
42 + kHash3Size
43 #endif
44 #endif
45 ;
46
47 #ifdef HASH_ARRAY_2
48 static const UInt32 kHash2Offset = kHashSize;
49 #ifdef HASH_ARRAY_3
50 static const UInt32 kHash3Offset = kHashSize + kHash2Size;
51 #endif
52 #endif
53
54 CMatchFinderHC::CMatchFinderHC():
55 _hash(0),
56 _cutValue(16)
57 {
58 }
59
60 void CMatchFinderHC::FreeThisClassMemory()
61 {
62 BigFree(_hash);
63 _hash = 0;
64 }
65
66 void CMatchFinderHC::FreeMemory()
67 {
68 FreeThisClassMemory();
69 CLZInWindow::Free();
70 }
71
72 CMatchFinderHC::~CMatchFinderHC()
73 {
74 FreeMemory();
75 }
76
77 STDMETHODIMP CMatchFinderHC::Create(UInt32 historySize, UInt32 keepAddBufferBefore,
78 UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
79 {
80 UInt32 sizeReserv = (historySize + keepAddBufferBefore +
81 matchMaxLen + keepAddBufferAfter) / 2 + 256;
82 if (CLZInWindow::Create(historySize + keepAddBufferBefore,
83 matchMaxLen + keepAddBufferAfter, sizeReserv))
84 {
85 if (historySize + 256 > kMaxValForNormalize)
86 {
87 FreeMemory();
88 return E_INVALIDARG;
89 }
90 _matchMaxLen = matchMaxLen;
91 UInt32 newCyclicBufferSize = historySize + 1;
92 if (_hash != 0 && newCyclicBufferSize == _cyclicBufferSize)
93 return S_OK;
94 FreeThisClassMemory();
95 _cyclicBufferSize = newCyclicBufferSize; // don't change it
96 _hash = (CIndex *)BigAlloc((kHashSizeSum + _cyclicBufferSize) * sizeof(CIndex));
97 if (_hash != 0)
98 return S_OK;
99 }
100 FreeMemory();
101 return E_OUTOFMEMORY;
102 }
103
104 static const UInt32 kEmptyHashValue = 0;
105
106 STDMETHODIMP CMatchFinderHC::Init(ISequentialInStream *stream)
107 {
108 RINOK(CLZInWindow::Init(stream));
109 for(UInt32 i = 0; i < kHashSizeSum; i++)
110 _hash[i] = kEmptyHashValue;
111 _cyclicBufferPos = 0;
112 ReduceOffsets(-1);
113 return S_OK;
114 }
115
116 STDMETHODIMP_(void) CMatchFinderHC::ReleaseStream()
117 {
118 // ReleaseStream();
119 }
120
121 #ifdef HASH_ARRAY_2
122 #ifdef HASH_ARRAY_3
123 inline UInt32 Hash(const Byte *pointer, UInt32 &hash2Value, UInt32 &hash3Value)
124 {
125 UInt32 temp = CCRC::Table[pointer[0]] ^ pointer[1];
126 hash2Value = temp & (kHash2Size - 1);
127 hash3Value = (temp ^ (UInt32(pointer[2]) << 8)) & (kHash3Size - 1);
128 return (temp ^ (UInt32(pointer[2]) << 8) ^ (CCRC::Table[pointer[3]] << 5)) &
129 (kHashSize - 1);
130 }
131 #else // no HASH_ARRAY_3
132 inline UInt32 Hash(const Byte *pointer, UInt32 &hash2Value)
133 {
134 UInt32 temp = CCRC::Table[pointer[0]] ^ pointer[1];
135 hash2Value = temp & (kHash2Size - 1);
136 return (temp ^ (UInt32(pointer[2]) << 8)) & (kHashSize - 1);;
137 }
138 #endif // HASH_ARRAY_3
139 #else // no HASH_ARRAY_2
140 #ifdef HASH_ZIP
141 inline UInt32 Hash(const Byte *pointer)
142 {
143 return ((UInt32(pointer[0]) << 8) ^
144 CCRC::Table[pointer[1]] ^ pointer[2]) & (kHashSize - 1);
145 }
146 #else // no HASH_ZIP
147 inline UInt32 Hash(const Byte *pointer)
148 {
149 return pointer[0] ^ (UInt32(pointer[1]) << 8);
150 }
151 #endif // HASH_ZIP
152 #endif // HASH_ARRAY_2
153
154
155 STDMETHODIMP_(UInt32) CMatchFinderHC::GetLongestMatch(UInt32 *distances)
156 {
157 UInt32 lenLimit;
158 if (_pos + _matchMaxLen <= _streamPos)
159 lenLimit = _matchMaxLen;
160 else
161 {
162 lenLimit = _streamPos - _pos;
163 if(lenLimit < kNumHashBytes)
164 return 0;
165 }
166
167 UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
168 Byte *cur = _buffer + _pos;
169
170 UInt32 maxLen = 0;
171
172 #ifdef HASH_ARRAY_2
173 UInt32 hash2Value;
174 #ifdef HASH_ARRAY_3
175 UInt32 hash3Value;
176 UInt32 hashValue = Hash(cur, hash2Value, hash3Value);
177 #else
178 UInt32 hashValue = Hash(cur, hash2Value);
179 #endif
180 #else
181 UInt32 hashValue = Hash(cur);
182 #endif
183 #ifdef HASH_ARRAY_2
184
185 UInt32 curMatch2 = _hash[kHash2Offset + hash2Value];
186 _hash[kHash2Offset + hash2Value] = _pos;
187 distances[2] = 0xFFFFFFFF;
188 if(curMatch2 > matchMinPos)
189 if (_buffer[curMatch2] == cur[0])
190 {
191 distances[2] = _pos - curMatch2 - 1;
192 maxLen = 2;
193 }
194
195 #ifdef HASH_ARRAY_3
196
197 UInt32 curMatch3 = _hash[kHash3Offset + hash3Value];
198 _hash[kHash3Offset + hash3Value] = _pos;
199 distances[3] = 0xFFFFFFFF;
200 if(curMatch3 > matchMinPos)
201 if (_buffer[curMatch3] == cur[0])
202 {
203 distances[3] = _pos - curMatch3 - 1;
204 maxLen = 3;
205 }
206
207 #endif
208 #endif
209
210 UInt32 curMatch = _hash[hashValue];
211 _hash[hashValue] = _pos;
212 CIndex *chain = _hash + kHashSizeSum;
213 chain[_cyclicBufferPos] = curMatch;
214 distances[kNumHashBytes] = 0xFFFFFFFF;
215 #ifdef THERE_ARE_DIRECT_HASH_BYTES
216 if (lenLimit == kNumHashDirectBytes)
217 {
218 if(curMatch > matchMinPos)
219 while (maxLen < kNumHashDirectBytes)
220 distances[++maxLen] = _pos - curMatch - 1;
221 }
222 else
223 #endif
224 {
225 UInt32 count = _cutValue;
226 do
227 {
228 if(curMatch <= matchMinPos)
229 break;
230 Byte *pby1 = _buffer + curMatch;
231 UInt32 currentLen = kNumHashDirectBytes;
232 do
233 {
234 if (pby1[currentLen] != cur[currentLen])
235 break;
236 }
237 while(++currentLen != lenLimit);
238
239 UInt32 delta = _pos - curMatch;
240 while (maxLen < currentLen)
241 distances[++maxLen] = delta - 1;
242 if(currentLen == lenLimit)
243 break;
244
245 UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?
246 (_cyclicBufferPos - delta):
247 (_cyclicBufferPos - delta + _cyclicBufferSize);
248
249 curMatch = chain[cyclicPos];
250 }
251 while(--count != 0);
252 }
253 #ifdef HASH_ARRAY_2
254 #ifdef HASH_ARRAY_3
255 if (distances[4] < distances[3])
256 distances[3] = distances[4];
257 #endif
258 if (distances[3] < distances[2])
259 distances[2] = distances[3];
260 #endif
261 return maxLen;
262 }
263
264 STDMETHODIMP_(void) CMatchFinderHC::DummyLongestMatch()
265 {
266 if (_streamPos - _pos < kNumHashBytes)
267 return;
268
269 Byte *cur = _buffer + _pos;
270
271 #ifdef HASH_ARRAY_2
272 UInt32 hash2Value;
273 #ifdef HASH_ARRAY_3
274 UInt32 hash3Value;
275 UInt32 hashValue = Hash(cur, hash2Value, hash3Value);
276 _hash[kHash3Offset + hash3Value] = _pos;
277 #else
278 UInt32 hashValue = Hash(cur, hash2Value);
279 #endif
280 _hash[kHash2Offset + hash2Value] = _pos;
281 #else
282 UInt32 hashValue = Hash(cur);
283 #endif
284
285 _hash[kHashSizeSum + _cyclicBufferPos] = _hash[hashValue];
286 _hash[hashValue] = _pos;
287 }
288
289 void CMatchFinderHC::Normalize()
290 {
291 UInt32 subValue = _pos - _cyclicBufferSize;
292 CIndex *items = _hash;
293 UInt32 numItems = kHashSizeSum + _cyclicBufferSize;
294 for (UInt32 i = 0; i < numItems; i++)
295 {
296 UInt32 value = items[i];
297 if (value <= subValue)
298 value = kEmptyHashValue;
299 else
300 value -= subValue;
301 items[i] = value;
302 }
303 ReduceOffsets(subValue);
304 }
305
306 STDMETHODIMP CMatchFinderHC::MovePos()
307 {
308 if (++_cyclicBufferPos == _cyclicBufferSize)
309 _cyclicBufferPos = 0;
310 RINOK(CLZInWindow::MovePos());
311 if (_pos == kMaxValForNormalize)
312 Normalize();
313 return S_OK;
314 }
315
316 STDMETHODIMP_(Byte) CMatchFinderHC::GetIndexByte(Int32 index)
317 { return CLZInWindow::GetIndexByte(index); }
318
319 STDMETHODIMP_(UInt32) CMatchFinderHC::GetMatchLen(Int32 index,
320 UInt32 back, UInt32 limit)
321 { return CLZInWindow::GetMatchLen(index, back, limit); }
322
323 STDMETHODIMP_(UInt32) CMatchFinderHC::GetNumAvailableBytes()
324 { return CLZInWindow::GetNumAvailableBytes(); }
325
326 STDMETHODIMP_(const Byte *) CMatchFinderHC::GetPointerToCurrentPos()
327 { return CLZInWindow::GetPointerToCurrentPos(); }
328
329 // IMatchFinderSetCallback
330 STDMETHODIMP CMatchFinderHC::SetCallback(IMatchFinderCallback *callback)
331 {
332 m_Callback = callback;
333 return S_OK;
334 }
335
336 void CMatchFinderHC::BeforeMoveBlock()
337 {
338 if (m_Callback)
339 m_Callback->BeforeChangingBufferPos();
340 CLZInWindow::BeforeMoveBlock();
341 }
342
343 void CMatchFinderHC::AfterMoveBlock()
344 {
345 if (m_Callback)
346 m_Callback->AfterChangingBufferPos();
347 CLZInWindow::AfterMoveBlock();
348 }
349
350 }