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