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