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