Annotation of elwix/tools/oldlzma/SRC/7zip/Compress/LZ/BinTree/BinTreeMain.h, revision 1.1
1.1 ! misho 1: // BinTreeMain.h
! 2:
! 3: #include "../../../../Common/Defs.h"
! 4: #include "../../../../Common/CRC.h"
! 5: #include "../../../../Common/Alloc.h"
! 6:
! 7: namespace BT_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 = 3;
! 22: static const UInt32 kNumHashBytes = 3;
! 23: static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
! 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: CMatchFinderBinTree::CMatchFinderBinTree():
! 55: _hash(0),
! 56: _cutValue(0xFF)
! 57: {
! 58: }
! 59:
! 60: void CMatchFinderBinTree::FreeThisClassMemory()
! 61: {
! 62: BigFree(_hash);
! 63: _hash = 0;
! 64: }
! 65:
! 66: void CMatchFinderBinTree::FreeMemory()
! 67: {
! 68: FreeThisClassMemory();
! 69: CLZInWindow::Free();
! 70: }
! 71:
! 72: CMatchFinderBinTree::~CMatchFinderBinTree()
! 73: {
! 74: FreeMemory();
! 75: }
! 76:
! 77: STDMETHODIMP CMatchFinderBinTree::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 * 2) * 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 CMatchFinderBinTree::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) CMatchFinderBinTree::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: hash2Value = (CCRC::Table[pointer[0]] ^ pointer[1]) & (kHash2Size - 1);
! 135: return ((UInt32(pointer[0]) << 16)) | ((UInt32(pointer[1]) << 8)) | pointer[2];
! 136: }
! 137: #endif // HASH_ARRAY_3
! 138: #else // no HASH_ARRAY_2
! 139: #ifdef HASH_ZIP
! 140: inline UInt32 Hash(const Byte *pointer)
! 141: {
! 142: return ((UInt32(pointer[0]) << 8) ^
! 143: CCRC::Table[pointer[1]] ^ pointer[2]) & (kHashSize - 1);
! 144: }
! 145: #else // no HASH_ZIP
! 146: inline UInt32 Hash(const Byte *pointer)
! 147: {
! 148: return pointer[0] ^ (UInt32(pointer[1]) << 8);
! 149: }
! 150: #endif // HASH_ZIP
! 151: #endif // HASH_ARRAY_2
! 152:
! 153: STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetLongestMatch(UInt32 *distances)
! 154: {
! 155: UInt32 lenLimit;
! 156: if (_pos + _matchMaxLen <= _streamPos)
! 157: lenLimit = _matchMaxLen;
! 158: else
! 159: {
! 160: lenLimit = _streamPos - _pos;
! 161: if(lenLimit < kNumHashBytes)
! 162: return 0;
! 163: }
! 164:
! 165: UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
! 166: Byte *cur = _buffer + _pos;
! 167:
! 168: UInt32 maxLen = 0;
! 169:
! 170: #ifdef HASH_ARRAY_2
! 171: UInt32 hash2Value;
! 172: #ifdef HASH_ARRAY_3
! 173: UInt32 hash3Value;
! 174: UInt32 hashValue = Hash(cur, hash2Value, hash3Value);
! 175: #else
! 176: UInt32 hashValue = Hash(cur, hash2Value);
! 177: #endif
! 178: #else
! 179: UInt32 hashValue = Hash(cur);
! 180: #endif
! 181:
! 182: UInt32 curMatch = _hash[hashValue];
! 183: #ifdef HASH_ARRAY_2
! 184: UInt32 curMatch2 = _hash[kHash2Offset + hash2Value];
! 185: #ifdef HASH_ARRAY_3
! 186: UInt32 curMatch3 = _hash[kHash3Offset + hash3Value];
! 187: #endif
! 188: _hash[kHash2Offset + hash2Value] = _pos;
! 189: distances[2] = 0xFFFFFFFF;
! 190: if(curMatch2 > matchMinPos)
! 191: if (_buffer[curMatch2] == cur[0])
! 192: {
! 193: distances[2] = _pos - curMatch2 - 1;
! 194: maxLen = 2;
! 195: }
! 196:
! 197: #ifdef HASH_ARRAY_3
! 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: #endif
! 207: #endif
! 208:
! 209: _hash[hashValue] = _pos;
! 210:
! 211: CIndex *son = _hash + kHashSizeSum;
! 212: CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1;
! 213: CIndex *ptr1 = son + (_cyclicBufferPos << 1);
! 214:
! 215: distances[kNumHashBytes] = 0xFFFFFFFF;
! 216:
! 217: #ifdef THERE_ARE_DIRECT_HASH_BYTES
! 218: if (lenLimit == kNumHashDirectBytes)
! 219: {
! 220: if(curMatch > matchMinPos)
! 221: while (maxLen < kNumHashDirectBytes)
! 222: distances[++maxLen] = _pos - curMatch - 1;
! 223: // We don't need tree in this case
! 224: }
! 225: else
! 226: #endif
! 227: {
! 228: UInt32 len0, len1;
! 229: len0 = len1 = kNumHashDirectBytes;
! 230: UInt32 count = _cutValue;
! 231: while(true)
! 232: {
! 233: if(curMatch <= matchMinPos || count-- == 0)
! 234: {
! 235: *ptr0 = kEmptyHashValue;
! 236: *ptr1 = kEmptyHashValue;
! 237: break;
! 238: }
! 239: Byte *pb = _buffer + curMatch;
! 240: UInt32 len = MyMin(len0, len1);
! 241: do
! 242: {
! 243: if (pb[len] != cur[len])
! 244: break;
! 245: }
! 246: while(++len != lenLimit);
! 247:
! 248: UInt32 delta = _pos - curMatch;
! 249: while (maxLen < len)
! 250: distances[++maxLen] = delta - 1;
! 251:
! 252: UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?
! 253: (_cyclicBufferPos - delta):
! 254: (_cyclicBufferPos - delta + _cyclicBufferSize);
! 255: CIndex *pair = son + (cyclicPos << 1);
! 256:
! 257: if (len != lenLimit)
! 258: {
! 259: if (pb[len] < cur[len])
! 260: {
! 261: *ptr1 = curMatch;
! 262: ptr1 = pair + 1;
! 263: curMatch = *ptr1;
! 264: len1 = len;
! 265: }
! 266: else
! 267: {
! 268: *ptr0 = curMatch;
! 269: ptr0 = pair;
! 270: curMatch = *ptr0;
! 271: len0 = len;
! 272: }
! 273: }
! 274: else
! 275: {
! 276: *ptr1 = pair[0];
! 277: *ptr0 = pair[1];
! 278: break;
! 279: }
! 280: }
! 281: }
! 282: #ifdef HASH_ARRAY_2
! 283: #ifdef HASH_ARRAY_3
! 284: if (distances[4] < distances[3])
! 285: distances[3] = distances[4];
! 286: #endif
! 287: if (distances[3] < distances[2])
! 288: distances[2] = distances[3];
! 289: #endif
! 290: return maxLen;
! 291: }
! 292:
! 293: STDMETHODIMP_(void) CMatchFinderBinTree::DummyLongestMatch()
! 294: {
! 295: UInt32 lenLimit;
! 296: if (_pos + _matchMaxLen <= _streamPos)
! 297: lenLimit = _matchMaxLen;
! 298: else
! 299: {
! 300: lenLimit = _streamPos - _pos;
! 301: if(lenLimit < kNumHashBytes)
! 302: return;
! 303: }
! 304: UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
! 305: Byte *cur = _buffer + _pos;
! 306:
! 307: #ifdef HASH_ARRAY_2
! 308: UInt32 hash2Value;
! 309: #ifdef HASH_ARRAY_3
! 310: UInt32 hash3Value;
! 311: UInt32 hashValue = Hash(cur, hash2Value, hash3Value);
! 312: _hash[kHash3Offset + hash3Value] = _pos;
! 313: #else
! 314: UInt32 hashValue = Hash(cur, hash2Value);
! 315: #endif
! 316: _hash[kHash2Offset + hash2Value] = _pos;
! 317: #else
! 318: UInt32 hashValue = Hash(cur);
! 319: #endif
! 320:
! 321: UInt32 curMatch = _hash[hashValue];
! 322: _hash[hashValue] = _pos;
! 323:
! 324: CIndex *son = _hash + kHashSizeSum;
! 325: CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1;
! 326: CIndex *ptr1 = son + (_cyclicBufferPos << 1);
! 327:
! 328: #ifdef THERE_ARE_DIRECT_HASH_BYTES
! 329: if (lenLimit != kNumHashDirectBytes)
! 330: #endif
! 331: {
! 332: UInt32 len0, len1;
! 333: len0 = len1 = kNumHashDirectBytes;
! 334: UInt32 count = _cutValue;
! 335: while(true)
! 336: {
! 337: if(curMatch <= matchMinPos || count-- == 0)
! 338: break;
! 339: Byte *pb = _buffer + curMatch;
! 340: UInt32 len = MyMin(len0, len1);
! 341: do
! 342: {
! 343: if (pb[len] != cur[len])
! 344: break;
! 345: }
! 346: while(++len != lenLimit);
! 347:
! 348: UInt32 delta = _pos - curMatch;
! 349: UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?
! 350: (_cyclicBufferPos - delta):
! 351: (_cyclicBufferPos - delta + _cyclicBufferSize);
! 352: CIndex *pair = son + (cyclicPos << 1);
! 353:
! 354: if (len != lenLimit)
! 355: {
! 356: if (pb[len] < cur[len])
! 357: {
! 358: *ptr1 = curMatch;
! 359: ptr1 = pair + 1;
! 360: curMatch = *ptr1;
! 361: len1 = len;
! 362: }
! 363: else
! 364: {
! 365: *ptr0 = curMatch;
! 366: ptr0 = pair;
! 367: curMatch = *ptr0;
! 368: len0 = len;
! 369: }
! 370: }
! 371: else
! 372: {
! 373: *ptr1 = pair[0];
! 374: *ptr0 = pair[1];
! 375: return;
! 376: }
! 377: }
! 378: }
! 379: *ptr0 = kEmptyHashValue;
! 380: *ptr1 = kEmptyHashValue;
! 381: }
! 382:
! 383: void CMatchFinderBinTree::Normalize()
! 384: {
! 385: UInt32 subValue = _pos - _cyclicBufferSize;
! 386: CIndex *items = _hash;
! 387: UInt32 numItems = (kHashSizeSum + _cyclicBufferSize * 2);
! 388: for (UInt32 i = 0; i < numItems; i++)
! 389: {
! 390: UInt32 value = items[i];
! 391: if (value <= subValue)
! 392: value = kEmptyHashValue;
! 393: else
! 394: value -= subValue;
! 395: items[i] = value;
! 396: }
! 397: ReduceOffsets(subValue);
! 398: }
! 399:
! 400: STDMETHODIMP CMatchFinderBinTree::MovePos()
! 401: {
! 402: if (++_cyclicBufferPos == _cyclicBufferSize)
! 403: _cyclicBufferPos = 0;
! 404: RINOK(CLZInWindow::MovePos());
! 405: if (_pos == kMaxValForNormalize)
! 406: Normalize();
! 407: return S_OK;
! 408: }
! 409:
! 410: STDMETHODIMP_(Byte) CMatchFinderBinTree::GetIndexByte(Int32 index)
! 411: { return CLZInWindow::GetIndexByte(index); }
! 412:
! 413: STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetMatchLen(Int32 index,
! 414: UInt32 back, UInt32 limit)
! 415: { return CLZInWindow::GetMatchLen(index, back, limit); }
! 416:
! 417: STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetNumAvailableBytes()
! 418: { return CLZInWindow::GetNumAvailableBytes(); }
! 419:
! 420: STDMETHODIMP_(const Byte *) CMatchFinderBinTree::GetPointerToCurrentPos()
! 421: { return CLZInWindow::GetPointerToCurrentPos(); }
! 422:
! 423: // IMatchFinderSetCallback
! 424: STDMETHODIMP CMatchFinderBinTree::SetCallback(IMatchFinderCallback *callback)
! 425: {
! 426: m_Callback = callback;
! 427: return S_OK;
! 428: }
! 429:
! 430: void CMatchFinderBinTree::BeforeMoveBlock()
! 431: {
! 432: if (m_Callback)
! 433: m_Callback->BeforeChangingBufferPos();
! 434: CLZInWindow::BeforeMoveBlock();
! 435: }
! 436:
! 437: void CMatchFinderBinTree::AfterMoveBlock()
! 438: {
! 439: if (m_Callback)
! 440: m_Callback->AfterChangingBufferPos();
! 441: CLZInWindow::AfterMoveBlock();
! 442: }
! 443:
! 444: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to BinTreeMain.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 / BinTree