Debian Codegraph @

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

raw
1 // PatMain.h
2
3 #include "../../../../Common/Defs.h"
4 #include "../../../../Common/Alloc.h"
5
6 namespace PAT_NAMESPACE {
7
8 STDMETHODIMP CPatricia::SetCallback(IMatchFinderCallback *callback)
9 {
10 m_Callback = callback;
11 return S_OK;
12 }
13
14 void CPatricia::BeforeMoveBlock()
15 {
16 if (m_Callback)
17 m_Callback->BeforeChangingBufferPos();
18 CLZInWindow::BeforeMoveBlock();
19 }
20
21 void CPatricia::AfterMoveBlock()
22 {
23 if (m_Callback)
24 m_Callback->AfterChangingBufferPos();
25 CLZInWindow::AfterMoveBlock();
26 }
27
28 const UInt32 kMatchStartValue2 = 2;
29 const UInt32 kDescendantEmptyValue2 = kMatchStartValue2 - 1;
30 const UInt32 kDescendantsNotInitilized2 = kDescendantEmptyValue2 - 1;
31
32 #ifdef __HASH_3
33
34 static const UInt32 kNumHashBytes = 3;
35 static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
36
37 static const UInt32 kNumHash2Bytes = 2;
38 static const UInt32 kHash2Size = 1 << (8 * kNumHash2Bytes);
39 static const UInt32 kPrevHashSize = kNumHash2Bytes;
40
41 #else
42
43 static const UInt32 kNumHashBytes = 2;
44 static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
45 static const UInt32 kPrevHashSize = 0;
46
47 #endif
48
49
50 CPatricia::CPatricia():
51 m_HashDescendants(0),
52 #ifdef __HASH_3
53 m_Hash2Descendants(0),
54 #endif
55 m_Nodes(0),
56 m_TmpBacks(0)
57 {
58 }
59
60 CPatricia::~CPatricia()
61 {
62 FreeMemory();
63 }
64
65 void CPatricia::FreeMemory()
66 {
67 MyFree(m_TmpBacks);
68 m_TmpBacks = 0;
69
70 ::BigFree(m_Nodes);
71 m_Nodes = 0;
72
73 ::BigFree(m_HashDescendants);
74 m_HashDescendants = 0;
75
76 #ifdef __HASH_3
77
78 ::BigFree(m_Hash2Descendants);
79 m_Hash2Descendants = 0;
80
81 CLZInWindow::Free();
82
83 #endif
84 }
85
86 STDMETHODIMP CPatricia::Create(UInt32 historySize, UInt32 keepAddBufferBefore,
87 UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
88 {
89 FreeMemory();
90 int kNumBitsInNumSameBits = sizeof(CSameBitsType) * 8;
91 if (kNumBitsInNumSameBits < 32 && ((matchMaxLen * MY_BYTE_SIZE) > ((UInt32)1 << kNumBitsInNumSameBits)))
92 return E_INVALIDARG;
93
94 const UInt32 kAlignMask = (1 << 16) - 1;
95 UInt32 windowReservSize = historySize;
96 windowReservSize += kAlignMask;
97 windowReservSize &= ~(kAlignMask);
98
99 const UInt32 kMinReservSize = (1 << 19);
100 if (windowReservSize < kMinReservSize)
101 windowReservSize = kMinReservSize;
102 windowReservSize += 256;
103
104 if (!CLZInWindow::Create(historySize + keepAddBufferBefore,
105 matchMaxLen + keepAddBufferAfter, windowReservSize))
106 return E_OUTOFMEMORY;
107
108 _sizeHistory = historySize;
109 _matchMaxLen = matchMaxLen;
110 m_HashDescendants = (CDescendant *)BigAlloc(kHashSize * sizeof(CDescendant));
111 if (m_HashDescendants == 0)
112 {
113 FreeMemory();
114 return E_OUTOFMEMORY;
115 }
116
117 #ifdef __HASH_3
118 m_Hash2Descendants = (CDescendant *)BigAlloc(kHash2Size * sizeof(CDescendant));
119 if (m_Hash2Descendants == 0)
120 {
121 FreeMemory();
122 return E_OUTOFMEMORY;
123 }
124 #endif
125
126 #ifdef __AUTO_REMOVE
127
128 #ifdef __HASH_3
129 m_NumNodes = historySize + _sizeHistory * 4 / 8 + (1 << 19);
130 #else
131 m_NumNodes = historySize + _sizeHistory * 4 / 8 + (1 << 10);
132 #endif
133
134 #else
135
136 UInt32 m_NumNodes = historySize;
137
138 #endif
139
140 const UInt32 kMaxNumNodes = UInt32(1) << (sizeof(CIndex) * 8 - 1);
141 if (m_NumNodes + 32 > kMaxNumNodes)
142 return E_INVALIDARG;
143
144 // m_Nodes = (CNode *)::BigAlloc((m_NumNodes + 2) * sizeof(CNode));
145 m_Nodes = (CNode *)::BigAlloc((m_NumNodes + 12) * sizeof(CNode));
146 if (m_Nodes == 0)
147 {
148 FreeMemory();
149 return E_OUTOFMEMORY;
150 }
151
152 m_TmpBacks = (UInt32 *)MyAlloc((_matchMaxLen + 1) * sizeof(UInt32));
153 if (m_TmpBacks == 0)
154 {
155 FreeMemory();
156 return E_OUTOFMEMORY;
157 }
158 return S_OK;
159 }
160
161 STDMETHODIMP CPatricia::Init(ISequentialInStream *aStream)
162 {
163 RINOK(CLZInWindow::Init(aStream));
164
165 // memset(m_HashDescendants, 0xFF, kHashSize * sizeof(m_HashDescendants[0]));
166
167 #ifdef __HASH_3
168 for (UInt32 i = 0; i < kHash2Size; i++)
169 m_Hash2Descendants[i].MatchPointer = kDescendantsNotInitilized2;
170 #else
171 for (UInt32 i = 0; i < kHashSize; i++)
172 m_HashDescendants[i].MakeEmpty();
173 #endif
174
175 m_Nodes[0].NextFreeNode = 1;
176 m_FreeNode = 0;
177 m_FreeNodeMax = 0;
178 #ifdef __AUTO_REMOVE
179 m_NumUsedNodes = 0;
180 #else
181 m_SpecialRemoveMode = false;
182 #endif
183 m_SpecialMode = false;
184 return S_OK;
185 }
186
187 STDMETHODIMP_(void) CPatricia::ReleaseStream()
188 {
189 // CLZInWindow::ReleaseStream();
190 }
191
192 // pos = _pos + kNumHashBytes
193 // fullCurrentLimit = currentLimit + kNumHashBytes
194 // fullMatchLen = matchLen + kNumHashBytes
195
196 void CPatricia::ChangeLastMatch(UInt32 hashValue)
197 {
198 UInt32 pos = _pos + kNumHashBytes - 1;
199 UInt32 descendantIndex;
200 const Byte *currentBytePointer = _buffer + pos;
201 UInt32 numLoadedBits = 0;
202 Byte curByte = 0; // = 0 to disable warning of GCC
203 CNodePointer node = &m_Nodes[m_HashDescendants[hashValue].NodePointer];
204
205 while(true)
206 {
207 UInt32 numSameBits = node->NumSameBits;
208 if(numSameBits > 0)
209 {
210 if (numLoadedBits < numSameBits)
211 {
212 numSameBits -= numLoadedBits;
213 currentBytePointer += (numSameBits / MY_BYTE_SIZE);
214 numSameBits %= MY_BYTE_SIZE;
215 curByte = *currentBytePointer++;
216 numLoadedBits = MY_BYTE_SIZE;
217 }
218 curByte >>= numSameBits;
219 numLoadedBits -= numSameBits;
220 }
221 if(numLoadedBits == 0)
222 {
223 curByte = *currentBytePointer++;
224 numLoadedBits = MY_BYTE_SIZE;
225 }
226 descendantIndex = (curByte & kSubNodesMask);
227 node->LastMatch = pos;
228 numLoadedBits -= kNumSubBits;
229 curByte >>= kNumSubBits;
230 if(node->Descendants[descendantIndex].IsNode())
231 node = &m_Nodes[node->Descendants[descendantIndex].NodePointer];
232 else
233 break;
234 }
235 node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;
236 }
237
238 UInt32 CPatricia::GetLongestMatch(UInt32 *distances)
239 {
240 UInt32 fullCurrentLimit;
241 if (_pos + _matchMaxLen <= _streamPos)
242 fullCurrentLimit = _matchMaxLen;
243 else
244 {
245 fullCurrentLimit = _streamPos - _pos;
246 if(fullCurrentLimit < kNumHashBytes)
247 return 0;
248 }
249 UInt32 pos = _pos + kNumHashBytes;
250
251 #ifdef __HASH_3
252 UInt32 hash2Value = ((UInt32(_buffer[_pos])) << 8) | _buffer[_pos + 1];
253 UInt32 hashValue = (hash2Value << 8) | _buffer[_pos + 2];
254 CDescendant &hash2Descendant = m_Hash2Descendants[hash2Value];
255 CDescendant &hashDescendant = m_HashDescendants[hashValue];
256 if(hash2Descendant.MatchPointer <= kDescendantEmptyValue2)
257 {
258 if(hash2Descendant.MatchPointer == kDescendantsNotInitilized2)
259 {
260 UInt32 base = hashValue & 0xFFFF00;
261 for (UInt32 i = 0; i < 0x100; i++)
262 m_HashDescendants[base + i].MakeEmpty();
263 }
264 hash2Descendant.MatchPointer = pos + kMatchStartValue2;
265 hashDescendant.MatchPointer = pos + kMatchStartValue;
266 return 0;
267 }
268
269 distances[kNumHash2Bytes] = pos - (hash2Descendant.MatchPointer - kMatchStartValue2) - 1;
270 hash2Descendant.MatchPointer = pos + kMatchStartValue2;
271 #ifdef __AUTO_REMOVE
272 if (distances[kNumHash2Bytes] >= _sizeHistory)
273 {
274 if (hashDescendant.IsNode())
275 RemoveNode(hashDescendant.NodePointer);
276 hashDescendant.MatchPointer = pos + kMatchStartValue;
277 return 0;
278 }
279 #endif
280 if (fullCurrentLimit == kNumHash2Bytes)
281 return kNumHash2Bytes;
282
283 #else
284 UInt32 hashValue = UInt32(GetIndexByte(1)) | (UInt32(GetIndexByte(0)) << 8);
285 CDescendant &hashDescendant = m_HashDescendants[hashValue];
286 #endif
287
288
289 if(m_SpecialMode)
290 {
291 if(hashDescendant.IsMatch())
292 m_NumNotChangedCycles = 0;
293 if(m_NumNotChangedCycles >= _sizeHistory - 1)
294 {
295 ChangeLastMatch(hashValue);
296 m_NumNotChangedCycles = 0;
297 }
298 if(GetIndexByte(fullCurrentLimit - 1) == GetIndexByte(fullCurrentLimit - 2))
299 {
300 if(hashDescendant.IsMatch())
301 hashDescendant.MatchPointer = pos + kMatchStartValue;
302 else
303 m_NumNotChangedCycles++;
304 for(UInt32 i = kNumHashBytes; i <= fullCurrentLimit; i++)
305 distances[i] = 0;
306 return fullCurrentLimit;
307 }
308 else if(m_NumNotChangedCycles > 0)
309 ChangeLastMatch(hashValue);
310 m_SpecialMode = false;
311 }
312
313 if(hashDescendant.IsEmpty())
314 {
315 hashDescendant.MatchPointer = pos + kMatchStartValue;
316 return kPrevHashSize;
317 }
318
319 UInt32 currentLimit = fullCurrentLimit - kNumHashBytes;
320
321 if(hashDescendant.IsMatch())
322 {
323 CMatchPointer matchPointer = hashDescendant.MatchPointer;
324 UInt32 backReal = pos - (matchPointer - kMatchStartValue);
325 UInt32 back = backReal - 1;
326 #ifdef __AUTO_REMOVE
327 if (back >= _sizeHistory)
328 {
329 hashDescendant.MatchPointer = pos + kMatchStartValue;
330 return kPrevHashSize;
331 }
332 #endif
333
334 UInt32 matchLen;
335 distances += kNumHashBytes;
336 Byte *buffer = _buffer + pos;
337 for(matchLen = 0; true; matchLen++)
338 {
339 *distances++ = back;
340 if (matchLen == currentLimit)
341 {
342 hashDescendant.MatchPointer = pos + kMatchStartValue;
343 return kNumHashBytes + matchLen;
344 }
345 if (buffer[matchLen] != buffer[(size_t)matchLen - backReal])
346 break;
347 }
348
349 // UInt32 matchLen = GetMatchLen(kNumHashBytes, back, currentLimit);
350
351 UInt32 fullMatchLen = matchLen + kNumHashBytes;
352 hashDescendant.NodePointer = m_FreeNode;
353 CNodePointer node = &m_Nodes[m_FreeNode];
354 m_FreeNode = node->NextFreeNode;
355 #ifdef __AUTO_REMOVE
356 m_NumUsedNodes++;
357 #endif
358 if (m_FreeNode > m_FreeNodeMax)
359 {
360 m_FreeNodeMax = m_FreeNode;
361 m_Nodes[m_FreeNode].NextFreeNode = m_FreeNode + 1;
362 }
363
364 for (UInt32 i = 0; i < kNumSubNodes; i++)
365 node->Descendants[i].NodePointer = kDescendantEmptyValue;
366 node->LastMatch = pos;
367
368 Byte byteNew = GetIndexByte(fullMatchLen);
369 Byte byteOld = GetIndexByte(fullMatchLen - backReal);
370 Byte bitsNew, bitsOld;
371 UInt32 numSameBits = matchLen * MY_BYTE_SIZE;
372 while (true)
373 {
374 bitsNew = (byteNew & kSubNodesMask);
375 bitsOld = (byteOld & kSubNodesMask);
376 if(bitsNew != bitsOld)
377 break;
378 byteNew >>= kNumSubBits;
379 byteOld >>= kNumSubBits;
380 numSameBits += kNumSubBits;
381 }
382 node->NumSameBits = CSameBitsType(numSameBits);
383 node->Descendants[bitsNew].MatchPointer = pos + kMatchStartValue;
384 node->Descendants[bitsOld].MatchPointer = matchPointer;
385 return fullMatchLen;
386 }
387 const Byte *baseCurrentBytePointer = _buffer + pos;
388 const Byte *currentBytePointer = baseCurrentBytePointer;
389 UInt32 numLoadedBits = 0;
390 Byte curByte = 0;
391 CIndex *nodePointerPointer = &hashDescendant.NodePointer;
392 CNodePointer node = &m_Nodes[*nodePointerPointer];
393 distances += kNumHashBytes;
394 const Byte *bytePointerLimit = baseCurrentBytePointer + currentLimit;
395 const Byte *currentAddingOffset = _buffer;
396
397 #ifdef __AUTO_REMOVE
398 UInt32 lowPos;
399 if (pos > _sizeHistory)
400 lowPos = pos - _sizeHistory;
401 else
402 lowPos = 0;
403 #endif
404
405 while(true)
406 {
407 #ifdef __AUTO_REMOVE
408 if (node->LastMatch < lowPos)
409 {
410 RemoveNode(*nodePointerPointer);
411 *nodePointerPointer = pos + kMatchStartValue;
412 if (currentBytePointer == baseCurrentBytePointer)
413 return kPrevHashSize;
414 return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
415 }
416 #endif
417 if(numLoadedBits == 0)
418 {
419 *distances++ = pos - node->LastMatch - 1;
420 if(currentBytePointer >= bytePointerLimit)
421 {
422 for (UInt32 i = 0; i < kNumSubNodes; i++)
423 node->Descendants[i].MatchPointer = pos + kMatchStartValue;
424 node->LastMatch = pos;
425 node->NumSameBits = 0;
426 return fullCurrentLimit;
427 }
428 curByte = (*currentBytePointer++);
429 currentAddingOffset++;
430 numLoadedBits = MY_BYTE_SIZE;
431 }
432 UInt32 numSameBits = node->NumSameBits;
433 if(numSameBits > 0)
434 {
435 Byte byteXOR = ((*(currentAddingOffset + node->LastMatch -1)) >>
436 (MY_BYTE_SIZE - numLoadedBits)) ^ curByte;
437 while(numLoadedBits <= numSameBits)
438 {
439 if(byteXOR != 0)
440 {
441 AddInternalNode(node, nodePointerPointer, curByte, byteXOR,
442 numSameBits, pos);
443 return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
444 }
445 *distances++ = pos - node->LastMatch - 1;
446 numSameBits -= numLoadedBits;
447 if(currentBytePointer >= bytePointerLimit)
448 {
449 for (UInt32 i = 0; i < kNumSubNodes; i++)
450 node->Descendants[i].MatchPointer = pos + kMatchStartValue;
451 node->LastMatch = pos;
452 node->NumSameBits = CSameBitsType(node->NumSameBits - numSameBits);
453 return fullCurrentLimit;
454 }
455 numLoadedBits = MY_BYTE_SIZE;
456 curByte = (*currentBytePointer++);
457 byteXOR = curByte ^ (*(currentAddingOffset + node->LastMatch));
458 currentAddingOffset++;
459 }
460 if((byteXOR & ((1 << numSameBits) - 1)) != 0)
461 {
462 AddInternalNode(node, nodePointerPointer, curByte, byteXOR,
463 numSameBits, pos);
464 return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
465 }
466 curByte >>= numSameBits;
467 numLoadedBits -= numSameBits;
468 }
469 UInt32 descendantIndex = (curByte & kSubNodesMask);
470 numLoadedBits -= kNumSubBits;
471 nodePointerPointer = &node->Descendants[descendantIndex].NodePointer;
472 UInt32 nextNodeIndex = *nodePointerPointer;
473 node->LastMatch = pos;
474 if (nextNodeIndex < kDescendantEmptyValue)
475 {
476 curByte >>= kNumSubBits;
477 node = &m_Nodes[nextNodeIndex];
478 }
479 else if (nextNodeIndex == kDescendantEmptyValue)
480 {
481 node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;
482 return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
483 }
484 else
485 break;
486 }
487
488 UInt32 descendantIndex = (curByte & kSubNodesMask);
489 curByte >>= kNumSubBits;
490 CMatchPointer matchPointer = node->Descendants[descendantIndex].MatchPointer;
491 CMatchPointer realMatchPointer;
492 realMatchPointer = matchPointer - kMatchStartValue;
493
494 #ifdef __AUTO_REMOVE
495 if (realMatchPointer < lowPos)
496 {
497 node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;
498 return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
499 }
500 #endif
501
502 Byte byteXOR;
503 UInt32 numSameBits = 0;
504 if(numLoadedBits != 0)
505 {
506 Byte matchByte = *(currentAddingOffset + realMatchPointer -1);
507 matchByte >>= (MY_BYTE_SIZE - numLoadedBits);
508 byteXOR = matchByte ^ curByte;
509 if(byteXOR != 0)
510 {
511 AddLeafNode(node, curByte, byteXOR, numSameBits, pos, descendantIndex);
512 return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
513 }
514 numSameBits += numLoadedBits;
515 }
516
517 const Byte *matchBytePointer = _buffer + realMatchPointer +
518 (currentBytePointer - baseCurrentBytePointer);
519 for(; currentBytePointer < bytePointerLimit; numSameBits += MY_BYTE_SIZE)
520 {
521 curByte = (*currentBytePointer++);
522 *distances++ = pos - realMatchPointer - 1;
523 byteXOR = curByte ^ (*matchBytePointer++);
524 if(byteXOR != 0)
525 {
526 AddLeafNode(node, curByte, byteXOR, numSameBits, pos, descendantIndex);
527 return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
528 }
529 }
530 *distances = pos - realMatchPointer - 1;
531 node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;
532
533 if(*distances == 0)
534 {
535 m_SpecialMode = true;
536 m_NumNotChangedCycles = 0;
537 }
538 return fullCurrentLimit;
539 }
540
541 STDMETHODIMP_(void) CPatricia::DummyLongestMatch()
542 {
543 GetLongestMatch(m_TmpBacks);
544 }
545
546
547 // ------------------------------------
548 // Remove Match
549
550 typedef Byte CRemoveDataWord;
551
552 static const int kSizeRemoveDataWordInBits = MY_BYTE_SIZE * sizeof(CRemoveDataWord);
553
554 #ifndef __AUTO_REMOVE
555
556 void CPatricia::RemoveMatch()
557 {
558 if(m_SpecialRemoveMode)
559 {
560 if(GetIndexByte(_matchMaxLen - 1 - _sizeHistory) ==
561 GetIndexByte(_matchMaxLen - _sizeHistory))
562 return;
563 m_SpecialRemoveMode = false;
564 }
565 UInt32 pos = _pos + kNumHashBytes - _sizeHistory;
566
567 #ifdef __HASH_3
568 const Byte *pp = _buffer + _pos - _sizeHistory;
569 UInt32 hash2Value = ((UInt32(pp[0])) << 8) | pp[1];
570 UInt32 hashValue = (hash2Value << 8) | pp[2];
571 CDescendant &hashDescendant = m_HashDescendants[hashValue];
572 CDescendant &hash2Descendant = m_Hash2Descendants[hash2Value];
573 if (hash2Descendant >= kMatchStartValue2)
574 if(hash2Descendant.MatchPointer == pos + kMatchStartValue2)
575 hash2Descendant.MatchPointer = kDescendantEmptyValue2;
576 #else
577 UInt32 hashValue = UInt32(GetIndexByte(1 - _sizeHistory)) |
578 (UInt32(GetIndexByte(0 - _sizeHistory)) << 8);
579 CDescendant &hashDescendant = m_HashDescendants[hashValue];
580 #endif
581
582 if(hashDescendant.IsEmpty())
583 return;
584 if(hashDescendant.IsMatch())
585 {
586 if(hashDescendant.MatchPointer == pos + kMatchStartValue)
587 hashDescendant.MakeEmpty();
588 return;
589 }
590
591 UInt32 descendantIndex;
592 const CRemoveDataWord *currentPointer = (const CRemoveDataWord *)(_buffer + pos);
593 UInt32 numLoadedBits = 0;
594 CRemoveDataWord curWord = 0; // = 0 to disable GCC warning
595
596 CIndex *nodePointerPointer = &hashDescendant.NodePointer;
597
598 CNodePointer node = &m_Nodes[hashDescendant.NodePointer];
599
600 while(true)
601 {
602 if(numLoadedBits == 0)
603 {
604 curWord = *currentPointer++;
605 numLoadedBits = kSizeRemoveDataWordInBits;
606 }
607 UInt32 numSameBits = node->NumSameBits;
608 if(numSameBits > 0)
609 {
610 if (numLoadedBits <= numSameBits)
611 {
612 numSameBits -= numLoadedBits;
613 currentPointer += (numSameBits / kSizeRemoveDataWordInBits);
614 numSameBits %= kSizeRemoveDataWordInBits;
615 curWord = *currentPointer++;
616 numLoadedBits = kSizeRemoveDataWordInBits;
617 }
618 curWord >>= numSameBits;
619 numLoadedBits -= numSameBits;
620 }
621 descendantIndex = (curWord & kSubNodesMask);
622 numLoadedBits -= kNumSubBits;
623 curWord >>= kNumSubBits;
624 UInt32 nextNodeIndex = node->Descendants[descendantIndex].NodePointer;
625 if (nextNodeIndex < kDescendantEmptyValue)
626 {
627 nodePointerPointer = &node->Descendants[descendantIndex].NodePointer;
628 node = &m_Nodes[nextNodeIndex];
629 }
630 else
631 break;
632 }
633 if (node->Descendants[descendantIndex].MatchPointer != pos + kMatchStartValue)
634 {
635 const Byte *currentBytePointer = _buffer + _pos - _sizeHistory;
636 const Byte *currentBytePointerLimit = currentBytePointer + _matchMaxLen;
637 for(;currentBytePointer < currentBytePointerLimit; currentBytePointer++)
638 if(*currentBytePointer != *(currentBytePointer+1))
639 return;
640 m_SpecialRemoveMode = true;
641 return;
642 }
643
644 UInt32 numNodes = 0, numMatches = 0;
645
646 UInt32 i;
647 for (i = 0; i < kNumSubNodes; i++)
648 {
649 UInt32 nodeIndex = node->Descendants[i].NodePointer;
650 if (nodeIndex < kDescendantEmptyValue)
651 numNodes++;
652 else if (nodeIndex > kDescendantEmptyValue)
653 numMatches++;
654 }
655 numMatches -= 1;
656 if (numNodes + numMatches > 1)
657 {
658 node->Descendants[descendantIndex].MakeEmpty();
659 return;
660 }
661 if(numNodes == 1)
662 {
663 UInt32 i;
664 for (i = 0; i < kNumSubNodes; i++)
665 if (node->Descendants[i].IsNode())
666 break;
667 UInt32 nextNodeIndex = node->Descendants[i].NodePointer;
668 CNodePointer nextNode = &m_Nodes[nextNodeIndex];
669 nextNode->NumSameBits += node->NumSameBits + kNumSubBits;
670 *node = *nextNode;
671
672 nextNode->NextFreeNode = m_FreeNode;
673 m_FreeNode = nextNodeIndex;
674 return;
675 }
676 UInt32 matchPointer = 0; // = 0 to disable GCC warning
677 for (i = 0; i < kNumSubNodes; i++)
678 if (node->Descendants[i].IsMatch() && i != descendantIndex)
679 {
680 matchPointer = node->Descendants[i].MatchPointer;
681 break;
682 }
683 node->NextFreeNode = m_FreeNode;
684 m_FreeNode = *nodePointerPointer;
685 *nodePointerPointer = matchPointer;
686 }
687 #endif
688
689
690 // Commented code is more correct, but it gives warning
691 // on GCC: (1 << 32)
692 // So we use kMatchStartValue twice:
693 // kMatchStartValue = UInt32(1) << (kNumBitsInIndex - 1);
694 // must be defined in Pat.h
695 /*
696 const UInt32 kNormalizeStartPos = (UInt32(1) << (kNumBitsInIndex)) -
697 kMatchStartValue - kNumHashBytes - 1;
698 */
699 const UInt32 kNormalizeStartPos = kMatchStartValue - kNumHashBytes - 1;
700
701 STDMETHODIMP CPatricia::MovePos()
702 {
703 #ifndef __AUTO_REMOVE
704 if(_pos >= _sizeHistory)
705 RemoveMatch();
706 #endif
707 RINOK(CLZInWindow::MovePos());
708 #ifdef __AUTO_REMOVE
709 if (m_NumUsedNodes >= m_NumNodes)
710 TestRemoveNodes();
711 #endif
712 if (_pos >= kNormalizeStartPos)
713 {
714 #ifdef __AUTO_REMOVE
715 TestRemoveNodesAndNormalize();
716 #else
717 Normalize();
718 #endif
719 }
720 return S_OK;
721 }
722
723 #ifndef __AUTO_REMOVE
724
725 void CPatricia::NormalizeDescendant(CDescendant &descendant, UInt32 subValue)
726 {
727 if (descendant.IsEmpty())
728 return;
729 if (descendant.IsMatch())
730 descendant.MatchPointer = descendant.MatchPointer - subValue;
731 else
732 {
733 CNode &node = m_Nodes[descendant.NodePointer];
734 node.LastMatch = node.LastMatch - subValue;
735 for (UInt32 i = 0; i < kNumSubNodes; i++)
736 NormalizeDescendant(node.Descendants[i], subValue);
737 }
738 }
739
740 void CPatricia::Normalize()
741 {
742 UInt32 subValue = _pos - _sizeHistory;
743 CLZInWindow::ReduceOffsets(subValue);
744
745 #ifdef __HASH_3
746
747 for(UInt32 hash = 0; hash < kHash2Size; hash++)
748 {
749 CDescendant &descendant = m_Hash2Descendants[hash];
750 if (descendant.MatchPointer != kDescendantsNotInitilized2)
751 {
752 UInt32 base = hash << 8;
753 for (UInt32 i = 0; i < 0x100; i++)
754 NormalizeDescendant(m_HashDescendants[base + i], subValue);
755 }
756 if (descendant.MatchPointer < kMatchStartValue2)
757 continue;
758 descendant.MatchPointer = descendant.MatchPointer - subValue;
759 }
760
761 #else
762
763 for(UInt32 hash = 0; hash < kHashSize; hash++)
764 NormalizeDescendant(m_HashDescendants[hash], subValue);
765
766 #endif
767
768 }
769
770 #else
771
772 void CPatricia::TestRemoveDescendant(CDescendant &descendant, UInt32 limitPos)
773 {
774 CNode &node = m_Nodes[descendant.NodePointer];
775 UInt32 numChilds = 0;
776 UInt32 childIndex = 0; // = 0 to disable GCC warning
777 for (UInt32 i = 0; i < kNumSubNodes; i++)
778 {
779 CDescendant &descendant2 = node.Descendants[i];
780 if (descendant2.IsEmpty())
781 continue;
782 if (descendant2.IsMatch())
783 {
784 if (descendant2.MatchPointer < limitPos)
785 descendant2.MakeEmpty();
786 else
787 {
788 numChilds++;
789 childIndex = i;
790 }
791 }
792 else
793 {
794 TestRemoveDescendant(descendant2, limitPos);
795 if (!descendant2.IsEmpty())
796 {
797 numChilds++;
798 childIndex = i;
799 }
800 }
801 }
802 if (numChilds > 1)
803 return;
804
805 CIndex nodePointerTemp = descendant.NodePointer;
806 if (numChilds == 1)
807 {
808 const CDescendant &descendant2 = node.Descendants[childIndex];
809 if (descendant2.IsNode())
810 m_Nodes[descendant2.NodePointer].NumSameBits += node.NumSameBits + kNumSubBits;
811 descendant = descendant2;
812 }
813 else
814 descendant.MakeEmpty();
815 node.NextFreeNode = m_FreeNode;
816 m_FreeNode = nodePointerTemp;
817 m_NumUsedNodes--;
818 }
819
820 void CPatricia::RemoveNode(UInt32 index)
821 {
822 CNode &node = m_Nodes[index];
823 for (UInt32 i = 0; i < kNumSubNodes; i++)
824 {
825 CDescendant &descendant2 = node.Descendants[i];
826 if (descendant2.IsNode())
827 RemoveNode(descendant2.NodePointer);
828 }
829 node.NextFreeNode = m_FreeNode;
830 m_FreeNode = index;
831 m_NumUsedNodes--;
832 }
833
834 void CPatricia::TestRemoveNodes()
835 {
836 UInt32 limitPos = kMatchStartValue + _pos - _sizeHistory + kNumHashBytes;
837
838 #ifdef __HASH_3
839
840 UInt32 limitPos2 = kMatchStartValue2 + _pos - _sizeHistory + kNumHashBytes;
841 for(UInt32 hash = 0; hash < kHash2Size; hash++)
842 {
843 CDescendant &descendant = m_Hash2Descendants[hash];
844 if (descendant.MatchPointer != kDescendantsNotInitilized2)
845 {
846 UInt32 base = hash << 8;
847 for (UInt32 i = 0; i < 0x100; i++)
848 {
849 CDescendant &descendant = m_HashDescendants[base + i];
850 if (descendant.IsEmpty())
851 continue;
852 if (descendant.IsMatch())
853 {
854 if (descendant.MatchPointer < limitPos)
855 descendant.MakeEmpty();
856 }
857 else
858 TestRemoveDescendant(descendant, limitPos);
859 }
860 }
861 if (descendant.MatchPointer < kMatchStartValue2)
862 continue;
863 if (descendant.MatchPointer < limitPos2)
864 descendant.MatchPointer = kDescendantEmptyValue2;
865 }
866
867 #else
868
869 for(UInt32 hash = 0; hash < kHashSize; hash++)
870 {
871 CDescendant &descendant = m_HashDescendants[hash];
872 if (descendant.IsEmpty())
873 continue;
874 if (descendant.IsMatch())
875 {
876 if (descendant.MatchPointer < limitPos)
877 descendant.MakeEmpty();
878 }
879 else
880 TestRemoveDescendant(descendant, limitPos);
881 }
882
883 #endif
884 }
885
886 void CPatricia::TestRemoveAndNormalizeDescendant(CDescendant &descendant,
887 UInt32 limitPos, UInt32 subValue)
888 {
889 if (descendant.IsEmpty())
890 return;
891 if (descendant.IsMatch())
892 {
893 if (descendant.MatchPointer < limitPos)
894 descendant.MakeEmpty();
895 else
896 descendant.MatchPointer = descendant.MatchPointer - subValue;
897 return;
898 }
899 CNode &node = m_Nodes[descendant.NodePointer];
900 UInt32 numChilds = 0;
901 UInt32 childIndex = 0; // = 0 to disable GCC warning
902 for (UInt32 i = 0; i < kNumSubNodes; i++)
903 {
904 CDescendant &descendant2 = node.Descendants[i];
905 TestRemoveAndNormalizeDescendant(descendant2, limitPos, subValue);
906 if (!descendant2.IsEmpty())
907 {
908 numChilds++;
909 childIndex = i;
910 }
911 }
912 if (numChilds > 1)
913 {
914 node.LastMatch = node.LastMatch - subValue;
915 return;
916 }
917
918 CIndex nodePointerTemp = descendant.NodePointer;
919 if (numChilds == 1)
920 {
921 const CDescendant &descendant2 = node.Descendants[childIndex];
922 if (descendant2.IsNode())
923 m_Nodes[descendant2.NodePointer].NumSameBits += node.NumSameBits + kNumSubBits;
924 descendant = descendant2;
925 }
926 else
927 descendant.MakeEmpty();
928 node.NextFreeNode = m_FreeNode;
929 m_FreeNode = nodePointerTemp;
930 m_NumUsedNodes--;
931 }
932
933 void CPatricia::TestRemoveNodesAndNormalize()
934 {
935 UInt32 subValue = _pos - _sizeHistory;
936 UInt32 limitPos = kMatchStartValue + _pos - _sizeHistory + kNumHashBytes;
937 CLZInWindow::ReduceOffsets(subValue);
938
939 #ifdef __HASH_3
940
941 UInt32 limitPos2 = kMatchStartValue2 + _pos - _sizeHistory + kNumHashBytes;
942 for(UInt32 hash = 0; hash < kHash2Size; hash++)
943 {
944 CDescendant &descendant = m_Hash2Descendants[hash];
945 if (descendant.MatchPointer != kDescendantsNotInitilized2)
946 {
947 UInt32 base = hash << 8;
948 for (UInt32 i = 0; i < 0x100; i++)
949 TestRemoveAndNormalizeDescendant(m_HashDescendants[base + i], limitPos, subValue);
950 }
951 if (descendant.MatchPointer < kMatchStartValue2)
952 continue;
953 if (descendant.MatchPointer < limitPos2)
954 descendant.MatchPointer = kDescendantEmptyValue2;
955 else
956 descendant.MatchPointer = descendant.MatchPointer - subValue;
957 }
958
959 #else
960
961 for(UInt32 hash = 0; hash < kHashSize; hash++)
962 TestRemoveAndNormalizeDescendant(m_HashDescendants[hash], limitPos, subValue);
963
964 #endif
965 }
966
967 #endif
968
969 STDMETHODIMP_(Byte) CPatricia::GetIndexByte(Int32 index)
970 {
971 return CLZInWindow::GetIndexByte(index);
972 }
973
974 STDMETHODIMP_(UInt32) CPatricia::GetMatchLen(Int32 index, UInt32 back, UInt32 limit)
975 {
976 return CLZInWindow::GetMatchLen(index, back, limit);
977 }
978
979 STDMETHODIMP_(UInt32) CPatricia::GetNumAvailableBytes()
980 {
981 return CLZInWindow::GetNumAvailableBytes();
982 }
983
984 STDMETHODIMP_(const Byte *) CPatricia::GetPointerToCurrentPos()
985 {
986 return CLZInWindow::GetPointerToCurrentPos();
987 }
988
989 }