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