Annotation of elwix/tools/oldlzma/SRC/7zip/Compress/LZ/Patricia/PatMain.h, revision 1.1.1.1
1.1 misho 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 + (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 + (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 + (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 + (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 + (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 + (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 + (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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to PatMain.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