1b1efbcd6SAlok Aggarwal /*
2b1efbcd6SAlok Aggarwal * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
3b1efbcd6SAlok Aggarwal * Use is subject to license terms.
4b1efbcd6SAlok Aggarwal */
5b1efbcd6SAlok Aggarwal
6b1efbcd6SAlok Aggarwal /* LzFind.c -- Match finder for LZ algorithms
7b1efbcd6SAlok Aggarwal 2008-10-04 : Igor Pavlov : Public domain */
8b1efbcd6SAlok Aggarwal
9b1efbcd6SAlok Aggarwal #include <string.h>
10b1efbcd6SAlok Aggarwal
11b1efbcd6SAlok Aggarwal #include "LzFind.h"
12b1efbcd6SAlok Aggarwal #include "LzHash.h"
13b1efbcd6SAlok Aggarwal
14b1efbcd6SAlok Aggarwal #define kEmptyHashValue 0
15b1efbcd6SAlok Aggarwal #define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
16b1efbcd6SAlok Aggarwal #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
17b1efbcd6SAlok Aggarwal #define kNormalizeMask (~(kNormalizeStepMin - 1))
18b1efbcd6SAlok Aggarwal #define kMaxHistorySize ((UInt32)3 << 30)
19b1efbcd6SAlok Aggarwal
20b1efbcd6SAlok Aggarwal #define kStartMaxLen 3
21b1efbcd6SAlok Aggarwal
LzInWindow_Free(CMatchFinder * p,ISzAlloc * alloc)22b1efbcd6SAlok Aggarwal static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
23b1efbcd6SAlok Aggarwal {
24b1efbcd6SAlok Aggarwal if (!p->directInput)
25b1efbcd6SAlok Aggarwal {
26b1efbcd6SAlok Aggarwal alloc->Free(alloc, p->bufferBase, 0);
27b1efbcd6SAlok Aggarwal p->bufferBase = 0;
28b1efbcd6SAlok Aggarwal }
29b1efbcd6SAlok Aggarwal }
30b1efbcd6SAlok Aggarwal
31b1efbcd6SAlok Aggarwal /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
32b1efbcd6SAlok Aggarwal
LzInWindow_Create(CMatchFinder * p,UInt32 keepSizeReserv,ISzAlloc * alloc)33b1efbcd6SAlok Aggarwal static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)
34b1efbcd6SAlok Aggarwal {
35b1efbcd6SAlok Aggarwal UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
36b1efbcd6SAlok Aggarwal if (p->directInput)
37b1efbcd6SAlok Aggarwal {
38b1efbcd6SAlok Aggarwal p->blockSize = blockSize;
39b1efbcd6SAlok Aggarwal return 1;
40b1efbcd6SAlok Aggarwal }
41b1efbcd6SAlok Aggarwal if (p->bufferBase == 0 || p->blockSize != blockSize)
42b1efbcd6SAlok Aggarwal {
43b1efbcd6SAlok Aggarwal LzInWindow_Free(p, alloc);
44b1efbcd6SAlok Aggarwal p->blockSize = blockSize;
45b1efbcd6SAlok Aggarwal p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
46b1efbcd6SAlok Aggarwal }
47b1efbcd6SAlok Aggarwal return (p->bufferBase != 0);
48b1efbcd6SAlok Aggarwal }
49b1efbcd6SAlok Aggarwal
MatchFinder_GetPointerToCurrentPos(CMatchFinder * p)50b1efbcd6SAlok Aggarwal Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
MatchFinder_GetIndexByte(CMatchFinder * p,Int32 index)51b1efbcd6SAlok Aggarwal Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[index]; }
52b1efbcd6SAlok Aggarwal
MatchFinder_GetNumAvailableBytes(CMatchFinder * p)53b1efbcd6SAlok Aggarwal UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
54b1efbcd6SAlok Aggarwal
MatchFinder_ReduceOffsets(CMatchFinder * p,UInt32 subValue)55b1efbcd6SAlok Aggarwal void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
56b1efbcd6SAlok Aggarwal {
57b1efbcd6SAlok Aggarwal p->posLimit -= subValue;
58b1efbcd6SAlok Aggarwal p->pos -= subValue;
59b1efbcd6SAlok Aggarwal p->streamPos -= subValue;
60b1efbcd6SAlok Aggarwal }
61b1efbcd6SAlok Aggarwal
MatchFinder_ReadBlock(CMatchFinder * p)62b1efbcd6SAlok Aggarwal static void MatchFinder_ReadBlock(CMatchFinder *p)
63b1efbcd6SAlok Aggarwal {
64b1efbcd6SAlok Aggarwal if (p->streamEndWasReached || p->result != SZ_OK)
65b1efbcd6SAlok Aggarwal return;
66b1efbcd6SAlok Aggarwal for (;;)
67b1efbcd6SAlok Aggarwal {
68b1efbcd6SAlok Aggarwal Byte *dest = p->buffer + (p->streamPos - p->pos);
69b1efbcd6SAlok Aggarwal size_t size = (p->bufferBase + p->blockSize - dest);
70b1efbcd6SAlok Aggarwal if (size == 0)
71b1efbcd6SAlok Aggarwal return;
72b1efbcd6SAlok Aggarwal p->result = p->stream->Read(p->stream, dest, &size);
73b1efbcd6SAlok Aggarwal if (p->result != SZ_OK)
74b1efbcd6SAlok Aggarwal return;
75b1efbcd6SAlok Aggarwal if (size == 0)
76b1efbcd6SAlok Aggarwal {
77b1efbcd6SAlok Aggarwal p->streamEndWasReached = 1;
78b1efbcd6SAlok Aggarwal return;
79b1efbcd6SAlok Aggarwal }
80b1efbcd6SAlok Aggarwal p->streamPos += (UInt32)size;
81b1efbcd6SAlok Aggarwal if (p->streamPos - p->pos > p->keepSizeAfter)
82b1efbcd6SAlok Aggarwal return;
83b1efbcd6SAlok Aggarwal }
84b1efbcd6SAlok Aggarwal }
85b1efbcd6SAlok Aggarwal
MatchFinder_MoveBlock(CMatchFinder * p)86b1efbcd6SAlok Aggarwal void MatchFinder_MoveBlock(CMatchFinder *p)
87b1efbcd6SAlok Aggarwal {
88b1efbcd6SAlok Aggarwal memmove(p->bufferBase,
89b1efbcd6SAlok Aggarwal p->buffer - p->keepSizeBefore,
90b1efbcd6SAlok Aggarwal (size_t)(p->streamPos - p->pos + p->keepSizeBefore));
91b1efbcd6SAlok Aggarwal p->buffer = p->bufferBase + p->keepSizeBefore;
92b1efbcd6SAlok Aggarwal }
93b1efbcd6SAlok Aggarwal
MatchFinder_NeedMove(CMatchFinder * p)94b1efbcd6SAlok Aggarwal int MatchFinder_NeedMove(CMatchFinder *p)
95b1efbcd6SAlok Aggarwal {
96b1efbcd6SAlok Aggarwal /* if (p->streamEndWasReached) return 0; */
97b1efbcd6SAlok Aggarwal return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
98b1efbcd6SAlok Aggarwal }
99b1efbcd6SAlok Aggarwal
MatchFinder_ReadIfRequired(CMatchFinder * p)100b1efbcd6SAlok Aggarwal void MatchFinder_ReadIfRequired(CMatchFinder *p)
101b1efbcd6SAlok Aggarwal {
102b1efbcd6SAlok Aggarwal if (p->streamEndWasReached)
103b1efbcd6SAlok Aggarwal return;
104b1efbcd6SAlok Aggarwal if (p->keepSizeAfter >= p->streamPos - p->pos)
105b1efbcd6SAlok Aggarwal MatchFinder_ReadBlock(p);
106b1efbcd6SAlok Aggarwal }
107b1efbcd6SAlok Aggarwal
MatchFinder_CheckAndMoveAndRead(CMatchFinder * p)108b1efbcd6SAlok Aggarwal static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
109b1efbcd6SAlok Aggarwal {
110b1efbcd6SAlok Aggarwal if (MatchFinder_NeedMove(p))
111b1efbcd6SAlok Aggarwal MatchFinder_MoveBlock(p);
112b1efbcd6SAlok Aggarwal MatchFinder_ReadBlock(p);
113b1efbcd6SAlok Aggarwal }
114b1efbcd6SAlok Aggarwal
MatchFinder_SetDefaultSettings(CMatchFinder * p)115b1efbcd6SAlok Aggarwal static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
116b1efbcd6SAlok Aggarwal {
117b1efbcd6SAlok Aggarwal p->cutValue = 32;
118b1efbcd6SAlok Aggarwal p->btMode = 1;
119b1efbcd6SAlok Aggarwal p->numHashBytes = 4;
120b1efbcd6SAlok Aggarwal /* p->skipModeBits = 0; */
121b1efbcd6SAlok Aggarwal p->directInput = 0;
122b1efbcd6SAlok Aggarwal p->bigHash = 0;
123b1efbcd6SAlok Aggarwal }
124b1efbcd6SAlok Aggarwal
125b1efbcd6SAlok Aggarwal #define kCrcPoly 0xEDB88320
126b1efbcd6SAlok Aggarwal
MatchFinder_Construct(CMatchFinder * p)127b1efbcd6SAlok Aggarwal void MatchFinder_Construct(CMatchFinder *p)
128b1efbcd6SAlok Aggarwal {
129b1efbcd6SAlok Aggarwal UInt32 i;
130b1efbcd6SAlok Aggarwal p->bufferBase = 0;
131b1efbcd6SAlok Aggarwal p->directInput = 0;
132b1efbcd6SAlok Aggarwal p->hash = 0;
133b1efbcd6SAlok Aggarwal MatchFinder_SetDefaultSettings(p);
134b1efbcd6SAlok Aggarwal
135b1efbcd6SAlok Aggarwal for (i = 0; i < 256; i++)
136b1efbcd6SAlok Aggarwal {
137b1efbcd6SAlok Aggarwal UInt32 r = i;
138b1efbcd6SAlok Aggarwal int j;
139b1efbcd6SAlok Aggarwal for (j = 0; j < 8; j++)
140b1efbcd6SAlok Aggarwal r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
141b1efbcd6SAlok Aggarwal p->crc[i] = r;
142b1efbcd6SAlok Aggarwal }
143b1efbcd6SAlok Aggarwal }
144b1efbcd6SAlok Aggarwal
MatchFinder_FreeThisClassMemory(CMatchFinder * p,ISzAlloc * alloc)145b1efbcd6SAlok Aggarwal static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
146b1efbcd6SAlok Aggarwal {
147b1efbcd6SAlok Aggarwal alloc->Free(alloc, p->hash, 0);
148b1efbcd6SAlok Aggarwal p->hash = 0;
149b1efbcd6SAlok Aggarwal }
150b1efbcd6SAlok Aggarwal
MatchFinder_Free(CMatchFinder * p,ISzAlloc * alloc)151b1efbcd6SAlok Aggarwal void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
152b1efbcd6SAlok Aggarwal {
153b1efbcd6SAlok Aggarwal MatchFinder_FreeThisClassMemory(p, alloc);
154b1efbcd6SAlok Aggarwal LzInWindow_Free(p, alloc);
155b1efbcd6SAlok Aggarwal }
156b1efbcd6SAlok Aggarwal
AllocRefs(UInt32 num,ISzAlloc * alloc)157b1efbcd6SAlok Aggarwal static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)
158b1efbcd6SAlok Aggarwal {
159b1efbcd6SAlok Aggarwal size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
160b1efbcd6SAlok Aggarwal if (sizeInBytes / sizeof(CLzRef) != num)
161b1efbcd6SAlok Aggarwal return 0;
162b1efbcd6SAlok Aggarwal return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
163b1efbcd6SAlok Aggarwal }
164b1efbcd6SAlok Aggarwal
MatchFinder_Create(CMatchFinder * p,UInt32 historySize,UInt32 keepAddBufferBefore,UInt32 matchMaxLen,UInt32 keepAddBufferAfter,ISzAlloc * alloc)165b1efbcd6SAlok Aggarwal int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
166b1efbcd6SAlok Aggarwal UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
167b1efbcd6SAlok Aggarwal ISzAlloc *alloc)
168b1efbcd6SAlok Aggarwal {
169b1efbcd6SAlok Aggarwal UInt32 sizeReserv;
170b1efbcd6SAlok Aggarwal if (historySize > kMaxHistorySize)
171b1efbcd6SAlok Aggarwal {
172b1efbcd6SAlok Aggarwal MatchFinder_Free(p, alloc);
173b1efbcd6SAlok Aggarwal return 0;
174b1efbcd6SAlok Aggarwal }
175b1efbcd6SAlok Aggarwal sizeReserv = historySize >> 1;
176b1efbcd6SAlok Aggarwal if (historySize > ((UInt32)2 << 30))
177b1efbcd6SAlok Aggarwal sizeReserv = historySize >> 2;
178b1efbcd6SAlok Aggarwal sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
179b1efbcd6SAlok Aggarwal
180b1efbcd6SAlok Aggarwal p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
181b1efbcd6SAlok Aggarwal p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
182b1efbcd6SAlok Aggarwal /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
183b1efbcd6SAlok Aggarwal if (LzInWindow_Create(p, sizeReserv, alloc))
184b1efbcd6SAlok Aggarwal {
185b1efbcd6SAlok Aggarwal UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;
186b1efbcd6SAlok Aggarwal UInt32 hs;
187b1efbcd6SAlok Aggarwal p->matchMaxLen = matchMaxLen;
188b1efbcd6SAlok Aggarwal {
189b1efbcd6SAlok Aggarwal p->fixedHashSize = 0;
190b1efbcd6SAlok Aggarwal if (p->numHashBytes == 2)
191b1efbcd6SAlok Aggarwal hs = (1 << 16) - 1;
192b1efbcd6SAlok Aggarwal else
193b1efbcd6SAlok Aggarwal {
194b1efbcd6SAlok Aggarwal hs = historySize - 1;
195b1efbcd6SAlok Aggarwal hs |= (hs >> 1);
196b1efbcd6SAlok Aggarwal hs |= (hs >> 2);
197b1efbcd6SAlok Aggarwal hs |= (hs >> 4);
198b1efbcd6SAlok Aggarwal hs |= (hs >> 8);
199b1efbcd6SAlok Aggarwal hs >>= 1;
200b1efbcd6SAlok Aggarwal /* hs >>= p->skipModeBits; */
201b1efbcd6SAlok Aggarwal hs |= 0xFFFF; /* don't change it! It's required for Deflate */
202b1efbcd6SAlok Aggarwal if (hs > (1 << 24))
203b1efbcd6SAlok Aggarwal {
204b1efbcd6SAlok Aggarwal if (p->numHashBytes == 3)
205b1efbcd6SAlok Aggarwal hs = (1 << 24) - 1;
206b1efbcd6SAlok Aggarwal else
207b1efbcd6SAlok Aggarwal hs >>= 1;
208b1efbcd6SAlok Aggarwal }
209b1efbcd6SAlok Aggarwal }
210b1efbcd6SAlok Aggarwal p->hashMask = hs;
211b1efbcd6SAlok Aggarwal hs++;
212b1efbcd6SAlok Aggarwal if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
213b1efbcd6SAlok Aggarwal if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
214b1efbcd6SAlok Aggarwal if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
215b1efbcd6SAlok Aggarwal hs += p->fixedHashSize;
216b1efbcd6SAlok Aggarwal }
217b1efbcd6SAlok Aggarwal
218b1efbcd6SAlok Aggarwal {
219b1efbcd6SAlok Aggarwal UInt32 prevSize = p->hashSizeSum + p->numSons;
220b1efbcd6SAlok Aggarwal UInt32 newSize;
221b1efbcd6SAlok Aggarwal p->historySize = historySize;
222b1efbcd6SAlok Aggarwal p->hashSizeSum = hs;
223b1efbcd6SAlok Aggarwal p->cyclicBufferSize = newCyclicBufferSize;
224b1efbcd6SAlok Aggarwal p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
225b1efbcd6SAlok Aggarwal newSize = p->hashSizeSum + p->numSons;
226b1efbcd6SAlok Aggarwal if (p->hash != 0 && prevSize == newSize)
227b1efbcd6SAlok Aggarwal return 1;
228b1efbcd6SAlok Aggarwal MatchFinder_FreeThisClassMemory(p, alloc);
229b1efbcd6SAlok Aggarwal p->hash = AllocRefs(newSize, alloc);
230b1efbcd6SAlok Aggarwal if (p->hash != 0)
231b1efbcd6SAlok Aggarwal {
232b1efbcd6SAlok Aggarwal p->son = p->hash + p->hashSizeSum;
233b1efbcd6SAlok Aggarwal return 1;
234b1efbcd6SAlok Aggarwal }
235b1efbcd6SAlok Aggarwal }
236b1efbcd6SAlok Aggarwal }
237b1efbcd6SAlok Aggarwal MatchFinder_Free(p, alloc);
238b1efbcd6SAlok Aggarwal return 0;
239b1efbcd6SAlok Aggarwal }
240b1efbcd6SAlok Aggarwal
MatchFinder_SetLimits(CMatchFinder * p)241b1efbcd6SAlok Aggarwal static void MatchFinder_SetLimits(CMatchFinder *p)
242b1efbcd6SAlok Aggarwal {
243b1efbcd6SAlok Aggarwal UInt32 limit = kMaxValForNormalize - p->pos;
244b1efbcd6SAlok Aggarwal UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
245b1efbcd6SAlok Aggarwal if (limit2 < limit)
246b1efbcd6SAlok Aggarwal limit = limit2;
247b1efbcd6SAlok Aggarwal limit2 = p->streamPos - p->pos;
248b1efbcd6SAlok Aggarwal if (limit2 <= p->keepSizeAfter)
249b1efbcd6SAlok Aggarwal {
250b1efbcd6SAlok Aggarwal if (limit2 > 0)
251b1efbcd6SAlok Aggarwal limit2 = 1;
252b1efbcd6SAlok Aggarwal }
253b1efbcd6SAlok Aggarwal else
254b1efbcd6SAlok Aggarwal limit2 -= p->keepSizeAfter;
255b1efbcd6SAlok Aggarwal if (limit2 < limit)
256b1efbcd6SAlok Aggarwal limit = limit2;
257b1efbcd6SAlok Aggarwal {
258b1efbcd6SAlok Aggarwal UInt32 lenLimit = p->streamPos - p->pos;
259b1efbcd6SAlok Aggarwal if (lenLimit > p->matchMaxLen)
260b1efbcd6SAlok Aggarwal lenLimit = p->matchMaxLen;
261b1efbcd6SAlok Aggarwal p->lenLimit = lenLimit;
262b1efbcd6SAlok Aggarwal }
263b1efbcd6SAlok Aggarwal p->posLimit = p->pos + limit;
264b1efbcd6SAlok Aggarwal }
265b1efbcd6SAlok Aggarwal
MatchFinder_Init(CMatchFinder * p)266b1efbcd6SAlok Aggarwal void MatchFinder_Init(CMatchFinder *p)
267b1efbcd6SAlok Aggarwal {
268b1efbcd6SAlok Aggarwal UInt32 i;
269b1efbcd6SAlok Aggarwal for (i = 0; i < p->hashSizeSum; i++)
270b1efbcd6SAlok Aggarwal p->hash[i] = kEmptyHashValue;
271b1efbcd6SAlok Aggarwal p->cyclicBufferPos = 0;
272b1efbcd6SAlok Aggarwal p->buffer = p->bufferBase;
273b1efbcd6SAlok Aggarwal p->pos = p->streamPos = p->cyclicBufferSize;
274b1efbcd6SAlok Aggarwal p->result = SZ_OK;
275b1efbcd6SAlok Aggarwal p->streamEndWasReached = 0;
276b1efbcd6SAlok Aggarwal MatchFinder_ReadBlock(p);
277b1efbcd6SAlok Aggarwal MatchFinder_SetLimits(p);
278b1efbcd6SAlok Aggarwal }
279b1efbcd6SAlok Aggarwal
MatchFinder_GetSubValue(CMatchFinder * p)280b1efbcd6SAlok Aggarwal static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
281b1efbcd6SAlok Aggarwal {
282b1efbcd6SAlok Aggarwal return (p->pos - p->historySize - 1) & kNormalizeMask;
283b1efbcd6SAlok Aggarwal }
284b1efbcd6SAlok Aggarwal
MatchFinder_Normalize3(UInt32 subValue,CLzRef * items,UInt32 numItems)285b1efbcd6SAlok Aggarwal void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
286b1efbcd6SAlok Aggarwal {
287b1efbcd6SAlok Aggarwal UInt32 i;
288b1efbcd6SAlok Aggarwal for (i = 0; i < numItems; i++)
289b1efbcd6SAlok Aggarwal {
290b1efbcd6SAlok Aggarwal UInt32 value = items[i];
291b1efbcd6SAlok Aggarwal if (value <= subValue)
292b1efbcd6SAlok Aggarwal value = kEmptyHashValue;
293b1efbcd6SAlok Aggarwal else
294b1efbcd6SAlok Aggarwal value -= subValue;
295b1efbcd6SAlok Aggarwal items[i] = value;
296b1efbcd6SAlok Aggarwal }
297b1efbcd6SAlok Aggarwal }
298b1efbcd6SAlok Aggarwal
MatchFinder_Normalize(CMatchFinder * p)299b1efbcd6SAlok Aggarwal static void MatchFinder_Normalize(CMatchFinder *p)
300b1efbcd6SAlok Aggarwal {
301b1efbcd6SAlok Aggarwal UInt32 subValue = MatchFinder_GetSubValue(p);
302b1efbcd6SAlok Aggarwal MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
303b1efbcd6SAlok Aggarwal MatchFinder_ReduceOffsets(p, subValue);
304b1efbcd6SAlok Aggarwal }
305b1efbcd6SAlok Aggarwal
MatchFinder_CheckLimits(CMatchFinder * p)306b1efbcd6SAlok Aggarwal static void MatchFinder_CheckLimits(CMatchFinder *p)
307b1efbcd6SAlok Aggarwal {
308b1efbcd6SAlok Aggarwal if (p->pos == kMaxValForNormalize)
309b1efbcd6SAlok Aggarwal MatchFinder_Normalize(p);
310b1efbcd6SAlok Aggarwal if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
311b1efbcd6SAlok Aggarwal MatchFinder_CheckAndMoveAndRead(p);
312b1efbcd6SAlok Aggarwal if (p->cyclicBufferPos == p->cyclicBufferSize)
313b1efbcd6SAlok Aggarwal p->cyclicBufferPos = 0;
314b1efbcd6SAlok Aggarwal MatchFinder_SetLimits(p);
315b1efbcd6SAlok Aggarwal }
316b1efbcd6SAlok Aggarwal
Hc_GetMatchesSpec(UInt32 lenLimit,UInt32 curMatch,UInt32 pos,const Byte * cur,CLzRef * son,UInt32 _cyclicBufferPos,UInt32 _cyclicBufferSize,UInt32 cutValue,UInt32 * distances,UInt32 maxLen)317b1efbcd6SAlok Aggarwal static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
318b1efbcd6SAlok Aggarwal UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
319b1efbcd6SAlok Aggarwal UInt32 *distances, UInt32 maxLen)
320b1efbcd6SAlok Aggarwal {
321b1efbcd6SAlok Aggarwal son[_cyclicBufferPos] = curMatch;
322b1efbcd6SAlok Aggarwal for (;;)
323b1efbcd6SAlok Aggarwal {
324b1efbcd6SAlok Aggarwal UInt32 delta = pos - curMatch;
325b1efbcd6SAlok Aggarwal if (cutValue-- == 0 || delta >= _cyclicBufferSize)
326b1efbcd6SAlok Aggarwal return distances;
327b1efbcd6SAlok Aggarwal {
328b1efbcd6SAlok Aggarwal const Byte *pb = cur - delta;
329b1efbcd6SAlok Aggarwal curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
330b1efbcd6SAlok Aggarwal if (pb[maxLen] == cur[maxLen] && *pb == *cur)
331b1efbcd6SAlok Aggarwal {
332b1efbcd6SAlok Aggarwal UInt32 len = 0;
333b1efbcd6SAlok Aggarwal while (++len != lenLimit)
334b1efbcd6SAlok Aggarwal if (pb[len] != cur[len])
335b1efbcd6SAlok Aggarwal break;
336b1efbcd6SAlok Aggarwal if (maxLen < len)
337b1efbcd6SAlok Aggarwal {
338b1efbcd6SAlok Aggarwal *distances++ = maxLen = len;
339b1efbcd6SAlok Aggarwal *distances++ = delta - 1;
340b1efbcd6SAlok Aggarwal if (len == lenLimit)
341b1efbcd6SAlok Aggarwal return distances;
342b1efbcd6SAlok Aggarwal }
343b1efbcd6SAlok Aggarwal }
344b1efbcd6SAlok Aggarwal }
345b1efbcd6SAlok Aggarwal }
346b1efbcd6SAlok Aggarwal }
347b1efbcd6SAlok Aggarwal
GetMatchesSpec1(UInt32 lenLimit,UInt32 curMatch,UInt32 pos,const Byte * cur,CLzRef * son,UInt32 _cyclicBufferPos,UInt32 _cyclicBufferSize,UInt32 cutValue,UInt32 * distances,UInt32 maxLen)348b1efbcd6SAlok Aggarwal UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
349b1efbcd6SAlok Aggarwal UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
350b1efbcd6SAlok Aggarwal UInt32 *distances, UInt32 maxLen)
351b1efbcd6SAlok Aggarwal {
352b1efbcd6SAlok Aggarwal CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
353b1efbcd6SAlok Aggarwal CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
354b1efbcd6SAlok Aggarwal UInt32 len0 = 0, len1 = 0;
355b1efbcd6SAlok Aggarwal for (;;)
356b1efbcd6SAlok Aggarwal {
357b1efbcd6SAlok Aggarwal UInt32 delta = pos - curMatch;
358b1efbcd6SAlok Aggarwal if (cutValue-- == 0 || delta >= _cyclicBufferSize)
359b1efbcd6SAlok Aggarwal {
360b1efbcd6SAlok Aggarwal *ptr0 = *ptr1 = kEmptyHashValue;
361b1efbcd6SAlok Aggarwal return distances;
362b1efbcd6SAlok Aggarwal }
363b1efbcd6SAlok Aggarwal {
364b1efbcd6SAlok Aggarwal CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
365b1efbcd6SAlok Aggarwal const Byte *pb = cur - delta;
366b1efbcd6SAlok Aggarwal UInt32 len = (len0 < len1 ? len0 : len1);
367b1efbcd6SAlok Aggarwal if (pb[len] == cur[len])
368b1efbcd6SAlok Aggarwal {
369b1efbcd6SAlok Aggarwal if (++len != lenLimit && pb[len] == cur[len])
370b1efbcd6SAlok Aggarwal while (++len != lenLimit)
371b1efbcd6SAlok Aggarwal if (pb[len] != cur[len])
372b1efbcd6SAlok Aggarwal break;
373b1efbcd6SAlok Aggarwal if (maxLen < len)
374b1efbcd6SAlok Aggarwal {
375b1efbcd6SAlok Aggarwal *distances++ = maxLen = len;
376b1efbcd6SAlok Aggarwal *distances++ = delta - 1;
377b1efbcd6SAlok Aggarwal if (len == lenLimit)
378b1efbcd6SAlok Aggarwal {
379b1efbcd6SAlok Aggarwal *ptr1 = pair[0];
380b1efbcd6SAlok Aggarwal *ptr0 = pair[1];
381b1efbcd6SAlok Aggarwal return distances;
382b1efbcd6SAlok Aggarwal }
383b1efbcd6SAlok Aggarwal }
384b1efbcd6SAlok Aggarwal }
385b1efbcd6SAlok Aggarwal if (pb[len] < cur[len])
386b1efbcd6SAlok Aggarwal {
387b1efbcd6SAlok Aggarwal *ptr1 = curMatch;
388b1efbcd6SAlok Aggarwal ptr1 = pair + 1;
389b1efbcd6SAlok Aggarwal curMatch = *ptr1;
390b1efbcd6SAlok Aggarwal len1 = len;
391b1efbcd6SAlok Aggarwal }
392b1efbcd6SAlok Aggarwal else
393b1efbcd6SAlok Aggarwal {
394b1efbcd6SAlok Aggarwal *ptr0 = curMatch;
395b1efbcd6SAlok Aggarwal ptr0 = pair;
396b1efbcd6SAlok Aggarwal curMatch = *ptr0;
397b1efbcd6SAlok Aggarwal len0 = len;
398b1efbcd6SAlok Aggarwal }
399b1efbcd6SAlok Aggarwal }
400b1efbcd6SAlok Aggarwal }
401b1efbcd6SAlok Aggarwal }
402b1efbcd6SAlok Aggarwal
SkipMatchesSpec(UInt32 lenLimit,UInt32 curMatch,UInt32 pos,const Byte * cur,CLzRef * son,UInt32 _cyclicBufferPos,UInt32 _cyclicBufferSize,UInt32 cutValue)403b1efbcd6SAlok Aggarwal static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
404b1efbcd6SAlok Aggarwal UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
405b1efbcd6SAlok Aggarwal {
406b1efbcd6SAlok Aggarwal CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
407b1efbcd6SAlok Aggarwal CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
408b1efbcd6SAlok Aggarwal UInt32 len0 = 0, len1 = 0;
409b1efbcd6SAlok Aggarwal for (;;)
410b1efbcd6SAlok Aggarwal {
411b1efbcd6SAlok Aggarwal UInt32 delta = pos - curMatch;
412b1efbcd6SAlok Aggarwal if (cutValue-- == 0 || delta >= _cyclicBufferSize)
413b1efbcd6SAlok Aggarwal {
414b1efbcd6SAlok Aggarwal *ptr0 = *ptr1 = kEmptyHashValue;
415b1efbcd6SAlok Aggarwal return;
416b1efbcd6SAlok Aggarwal }
417b1efbcd6SAlok Aggarwal {
418b1efbcd6SAlok Aggarwal CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
419b1efbcd6SAlok Aggarwal const Byte *pb = cur - delta;
420b1efbcd6SAlok Aggarwal UInt32 len = (len0 < len1 ? len0 : len1);
421b1efbcd6SAlok Aggarwal if (pb[len] == cur[len])
422b1efbcd6SAlok Aggarwal {
423b1efbcd6SAlok Aggarwal while (++len != lenLimit)
424b1efbcd6SAlok Aggarwal if (pb[len] != cur[len])
425b1efbcd6SAlok Aggarwal break;
426b1efbcd6SAlok Aggarwal {
427b1efbcd6SAlok Aggarwal if (len == lenLimit)
428b1efbcd6SAlok Aggarwal {
429b1efbcd6SAlok Aggarwal *ptr1 = pair[0];
430b1efbcd6SAlok Aggarwal *ptr0 = pair[1];
431b1efbcd6SAlok Aggarwal return;
432b1efbcd6SAlok Aggarwal }
433b1efbcd6SAlok Aggarwal }
434b1efbcd6SAlok Aggarwal }
435b1efbcd6SAlok Aggarwal if (pb[len] < cur[len])
436b1efbcd6SAlok Aggarwal {
437b1efbcd6SAlok Aggarwal *ptr1 = curMatch;
438b1efbcd6SAlok Aggarwal ptr1 = pair + 1;
439b1efbcd6SAlok Aggarwal curMatch = *ptr1;
440b1efbcd6SAlok Aggarwal len1 = len;
441b1efbcd6SAlok Aggarwal }
442b1efbcd6SAlok Aggarwal else
443b1efbcd6SAlok Aggarwal {
444b1efbcd6SAlok Aggarwal *ptr0 = curMatch;
445b1efbcd6SAlok Aggarwal ptr0 = pair;
446b1efbcd6SAlok Aggarwal curMatch = *ptr0;
447b1efbcd6SAlok Aggarwal len0 = len;
448b1efbcd6SAlok Aggarwal }
449b1efbcd6SAlok Aggarwal }
450b1efbcd6SAlok Aggarwal }
451b1efbcd6SAlok Aggarwal }
452b1efbcd6SAlok Aggarwal
453b1efbcd6SAlok Aggarwal #define MOVE_POS \
454b1efbcd6SAlok Aggarwal ++p->cyclicBufferPos; \
455b1efbcd6SAlok Aggarwal p->buffer++; \
456b1efbcd6SAlok Aggarwal if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
457b1efbcd6SAlok Aggarwal
458b1efbcd6SAlok Aggarwal #define MOVE_POS_RET MOVE_POS return offset;
459b1efbcd6SAlok Aggarwal
MatchFinder_MovePos(CMatchFinder * p)460b1efbcd6SAlok Aggarwal static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
461b1efbcd6SAlok Aggarwal
462b1efbcd6SAlok Aggarwal #define GET_MATCHES_HEADER2(minLen, ret_op) \
463b1efbcd6SAlok Aggarwal UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \
464b1efbcd6SAlok Aggarwal lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
465b1efbcd6SAlok Aggarwal cur = p->buffer;
466b1efbcd6SAlok Aggarwal
467b1efbcd6SAlok Aggarwal #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
468b1efbcd6SAlok Aggarwal #define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue)
469b1efbcd6SAlok Aggarwal
470b1efbcd6SAlok Aggarwal #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
471b1efbcd6SAlok Aggarwal
472b1efbcd6SAlok Aggarwal #define GET_MATCHES_FOOTER(offset, maxLen) \
473b1efbcd6SAlok Aggarwal offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
474b1efbcd6SAlok Aggarwal distances + offset, maxLen) - distances); MOVE_POS_RET;
475b1efbcd6SAlok Aggarwal
476b1efbcd6SAlok Aggarwal #define SKIP_FOOTER \
477b1efbcd6SAlok Aggarwal SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
478b1efbcd6SAlok Aggarwal
Bt2_MatchFinder_GetMatches(CMatchFinder * p,UInt32 * distances)479b1efbcd6SAlok Aggarwal static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
480b1efbcd6SAlok Aggarwal {
481b1efbcd6SAlok Aggarwal UInt32 offset;
482b1efbcd6SAlok Aggarwal GET_MATCHES_HEADER(2)
483b1efbcd6SAlok Aggarwal HASH2_CALC;
484b1efbcd6SAlok Aggarwal curMatch = p->hash[hashValue];
485b1efbcd6SAlok Aggarwal p->hash[hashValue] = p->pos;
486b1efbcd6SAlok Aggarwal offset = 0;
487b1efbcd6SAlok Aggarwal GET_MATCHES_FOOTER(offset, 1)
488b1efbcd6SAlok Aggarwal }
489b1efbcd6SAlok Aggarwal
Bt3Zip_MatchFinder_GetMatches(CMatchFinder * p,UInt32 * distances)490b1efbcd6SAlok Aggarwal UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
491b1efbcd6SAlok Aggarwal {
492b1efbcd6SAlok Aggarwal UInt32 offset;
493b1efbcd6SAlok Aggarwal GET_MATCHES_HEADER(3)
494b1efbcd6SAlok Aggarwal HASH_ZIP_CALC;
495b1efbcd6SAlok Aggarwal curMatch = p->hash[hashValue];
496b1efbcd6SAlok Aggarwal p->hash[hashValue] = p->pos;
497b1efbcd6SAlok Aggarwal offset = 0;
498b1efbcd6SAlok Aggarwal GET_MATCHES_FOOTER(offset, 2)
499b1efbcd6SAlok Aggarwal }
500b1efbcd6SAlok Aggarwal
Bt3_MatchFinder_GetMatches(CMatchFinder * p,UInt32 * distances)501b1efbcd6SAlok Aggarwal static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
502b1efbcd6SAlok Aggarwal {
503b1efbcd6SAlok Aggarwal UInt32 hash2Value, delta2, maxLen, offset;
504b1efbcd6SAlok Aggarwal GET_MATCHES_HEADER(3)
505b1efbcd6SAlok Aggarwal
506b1efbcd6SAlok Aggarwal HASH3_CALC;
507b1efbcd6SAlok Aggarwal
508b1efbcd6SAlok Aggarwal delta2 = p->pos - p->hash[hash2Value];
509b1efbcd6SAlok Aggarwal curMatch = p->hash[kFix3HashSize + hashValue];
510*55fea89dSDan Cross
511b1efbcd6SAlok Aggarwal p->hash[hash2Value] =
512b1efbcd6SAlok Aggarwal p->hash[kFix3HashSize + hashValue] = p->pos;
513b1efbcd6SAlok Aggarwal
514b1efbcd6SAlok Aggarwal
515b1efbcd6SAlok Aggarwal maxLen = 2;
516b1efbcd6SAlok Aggarwal offset = 0;
517b1efbcd6SAlok Aggarwal if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
518b1efbcd6SAlok Aggarwal {
519b1efbcd6SAlok Aggarwal for (; maxLen != lenLimit; maxLen++)
520b1efbcd6SAlok Aggarwal if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
521b1efbcd6SAlok Aggarwal break;
522b1efbcd6SAlok Aggarwal distances[0] = maxLen;
523b1efbcd6SAlok Aggarwal distances[1] = delta2 - 1;
524b1efbcd6SAlok Aggarwal offset = 2;
525b1efbcd6SAlok Aggarwal if (maxLen == lenLimit)
526b1efbcd6SAlok Aggarwal {
527b1efbcd6SAlok Aggarwal SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
528b1efbcd6SAlok Aggarwal MOVE_POS_RET;
529b1efbcd6SAlok Aggarwal }
530b1efbcd6SAlok Aggarwal }
531b1efbcd6SAlok Aggarwal GET_MATCHES_FOOTER(offset, maxLen)
532b1efbcd6SAlok Aggarwal }
533b1efbcd6SAlok Aggarwal
Bt4_MatchFinder_GetMatches(CMatchFinder * p,UInt32 * distances)534b1efbcd6SAlok Aggarwal static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
535b1efbcd6SAlok Aggarwal {
536b1efbcd6SAlok Aggarwal UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
537b1efbcd6SAlok Aggarwal GET_MATCHES_HEADER(4)
538b1efbcd6SAlok Aggarwal
539b1efbcd6SAlok Aggarwal HASH4_CALC;
540b1efbcd6SAlok Aggarwal
541b1efbcd6SAlok Aggarwal delta2 = p->pos - p->hash[ hash2Value];
542b1efbcd6SAlok Aggarwal delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
543b1efbcd6SAlok Aggarwal curMatch = p->hash[kFix4HashSize + hashValue];
544*55fea89dSDan Cross
545b1efbcd6SAlok Aggarwal p->hash[ hash2Value] =
546b1efbcd6SAlok Aggarwal p->hash[kFix3HashSize + hash3Value] =
547b1efbcd6SAlok Aggarwal p->hash[kFix4HashSize + hashValue] = p->pos;
548b1efbcd6SAlok Aggarwal
549b1efbcd6SAlok Aggarwal maxLen = 1;
550b1efbcd6SAlok Aggarwal offset = 0;
551b1efbcd6SAlok Aggarwal if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
552b1efbcd6SAlok Aggarwal {
553b1efbcd6SAlok Aggarwal distances[0] = maxLen = 2;
554b1efbcd6SAlok Aggarwal distances[1] = delta2 - 1;
555b1efbcd6SAlok Aggarwal offset = 2;
556b1efbcd6SAlok Aggarwal }
557b1efbcd6SAlok Aggarwal if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
558b1efbcd6SAlok Aggarwal {
559b1efbcd6SAlok Aggarwal maxLen = 3;
560b1efbcd6SAlok Aggarwal distances[offset + 1] = delta3 - 1;
561b1efbcd6SAlok Aggarwal offset += 2;
562b1efbcd6SAlok Aggarwal delta2 = delta3;
563b1efbcd6SAlok Aggarwal }
564b1efbcd6SAlok Aggarwal if (offset != 0)
565b1efbcd6SAlok Aggarwal {
566b1efbcd6SAlok Aggarwal for (; maxLen != lenLimit; maxLen++)
567b1efbcd6SAlok Aggarwal if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
568b1efbcd6SAlok Aggarwal break;
569b1efbcd6SAlok Aggarwal distances[offset - 2] = maxLen;
570b1efbcd6SAlok Aggarwal if (maxLen == lenLimit)
571b1efbcd6SAlok Aggarwal {
572b1efbcd6SAlok Aggarwal SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
573b1efbcd6SAlok Aggarwal MOVE_POS_RET;
574b1efbcd6SAlok Aggarwal }
575b1efbcd6SAlok Aggarwal }
576b1efbcd6SAlok Aggarwal if (maxLen < 3)
577b1efbcd6SAlok Aggarwal maxLen = 3;
578b1efbcd6SAlok Aggarwal GET_MATCHES_FOOTER(offset, maxLen)
579b1efbcd6SAlok Aggarwal }
580b1efbcd6SAlok Aggarwal
Hc4_MatchFinder_GetMatches(CMatchFinder * p,UInt32 * distances)581b1efbcd6SAlok Aggarwal static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
582b1efbcd6SAlok Aggarwal {
583b1efbcd6SAlok Aggarwal UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
584b1efbcd6SAlok Aggarwal GET_MATCHES_HEADER(4)
585b1efbcd6SAlok Aggarwal
586b1efbcd6SAlok Aggarwal HASH4_CALC;
587b1efbcd6SAlok Aggarwal
588b1efbcd6SAlok Aggarwal delta2 = p->pos - p->hash[ hash2Value];
589b1efbcd6SAlok Aggarwal delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
590b1efbcd6SAlok Aggarwal curMatch = p->hash[kFix4HashSize + hashValue];
591b1efbcd6SAlok Aggarwal
592b1efbcd6SAlok Aggarwal p->hash[ hash2Value] =
593b1efbcd6SAlok Aggarwal p->hash[kFix3HashSize + hash3Value] =
594b1efbcd6SAlok Aggarwal p->hash[kFix4HashSize + hashValue] = p->pos;
595b1efbcd6SAlok Aggarwal
596b1efbcd6SAlok Aggarwal maxLen = 1;
597b1efbcd6SAlok Aggarwal offset = 0;
598b1efbcd6SAlok Aggarwal if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
599b1efbcd6SAlok Aggarwal {
600b1efbcd6SAlok Aggarwal distances[0] = maxLen = 2;
601b1efbcd6SAlok Aggarwal distances[1] = delta2 - 1;
602b1efbcd6SAlok Aggarwal offset = 2;
603b1efbcd6SAlok Aggarwal }
604b1efbcd6SAlok Aggarwal if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
605b1efbcd6SAlok Aggarwal {
606b1efbcd6SAlok Aggarwal maxLen = 3;
607b1efbcd6SAlok Aggarwal distances[offset + 1] = delta3 - 1;
608b1efbcd6SAlok Aggarwal offset += 2;
609b1efbcd6SAlok Aggarwal delta2 = delta3;
610b1efbcd6SAlok Aggarwal }
611b1efbcd6SAlok Aggarwal if (offset != 0)
612b1efbcd6SAlok Aggarwal {
613b1efbcd6SAlok Aggarwal for (; maxLen != lenLimit; maxLen++)
614b1efbcd6SAlok Aggarwal if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
615b1efbcd6SAlok Aggarwal break;
616b1efbcd6SAlok Aggarwal distances[offset - 2] = maxLen;
617b1efbcd6SAlok Aggarwal if (maxLen == lenLimit)
618b1efbcd6SAlok Aggarwal {
619b1efbcd6SAlok Aggarwal p->son[p->cyclicBufferPos] = curMatch;
620b1efbcd6SAlok Aggarwal MOVE_POS_RET;
621b1efbcd6SAlok Aggarwal }
622b1efbcd6SAlok Aggarwal }
623b1efbcd6SAlok Aggarwal if (maxLen < 3)
624b1efbcd6SAlok Aggarwal maxLen = 3;
625b1efbcd6SAlok Aggarwal offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
626b1efbcd6SAlok Aggarwal distances + offset, maxLen) - (distances));
627b1efbcd6SAlok Aggarwal MOVE_POS_RET
628b1efbcd6SAlok Aggarwal }
629b1efbcd6SAlok Aggarwal
Hc3Zip_MatchFinder_GetMatches(CMatchFinder * p,UInt32 * distances)630b1efbcd6SAlok Aggarwal UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
631b1efbcd6SAlok Aggarwal {
632b1efbcd6SAlok Aggarwal UInt32 offset;
633b1efbcd6SAlok Aggarwal GET_MATCHES_HEADER(3)
634b1efbcd6SAlok Aggarwal HASH_ZIP_CALC;
635b1efbcd6SAlok Aggarwal curMatch = p->hash[hashValue];
636b1efbcd6SAlok Aggarwal p->hash[hashValue] = p->pos;
637b1efbcd6SAlok Aggarwal offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
638b1efbcd6SAlok Aggarwal distances, 2) - (distances));
639b1efbcd6SAlok Aggarwal MOVE_POS_RET
640b1efbcd6SAlok Aggarwal }
641b1efbcd6SAlok Aggarwal
Bt2_MatchFinder_Skip(CMatchFinder * p,UInt32 num)642b1efbcd6SAlok Aggarwal static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
643b1efbcd6SAlok Aggarwal {
644b1efbcd6SAlok Aggarwal do
645b1efbcd6SAlok Aggarwal {
646b1efbcd6SAlok Aggarwal SKIP_HEADER(2)
647b1efbcd6SAlok Aggarwal HASH2_CALC;
648b1efbcd6SAlok Aggarwal curMatch = p->hash[hashValue];
649b1efbcd6SAlok Aggarwal p->hash[hashValue] = p->pos;
650b1efbcd6SAlok Aggarwal SKIP_FOOTER
651b1efbcd6SAlok Aggarwal }
652b1efbcd6SAlok Aggarwal while (--num != 0);
653b1efbcd6SAlok Aggarwal }
654b1efbcd6SAlok Aggarwal
Bt3Zip_MatchFinder_Skip(CMatchFinder * p,UInt32 num)655b1efbcd6SAlok Aggarwal void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
656b1efbcd6SAlok Aggarwal {
657b1efbcd6SAlok Aggarwal do
658b1efbcd6SAlok Aggarwal {
659b1efbcd6SAlok Aggarwal SKIP_HEADER(3)
660b1efbcd6SAlok Aggarwal HASH_ZIP_CALC;
661b1efbcd6SAlok Aggarwal curMatch = p->hash[hashValue];
662b1efbcd6SAlok Aggarwal p->hash[hashValue] = p->pos;
663b1efbcd6SAlok Aggarwal SKIP_FOOTER
664b1efbcd6SAlok Aggarwal }
665b1efbcd6SAlok Aggarwal while (--num != 0);
666b1efbcd6SAlok Aggarwal }
667b1efbcd6SAlok Aggarwal
Bt3_MatchFinder_Skip(CMatchFinder * p,UInt32 num)668b1efbcd6SAlok Aggarwal static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
669b1efbcd6SAlok Aggarwal {
670b1efbcd6SAlok Aggarwal do
671b1efbcd6SAlok Aggarwal {
672b1efbcd6SAlok Aggarwal UInt32 hash2Value;
673b1efbcd6SAlok Aggarwal SKIP_HEADER(3)
674b1efbcd6SAlok Aggarwal HASH3_CALC;
675b1efbcd6SAlok Aggarwal curMatch = p->hash[kFix3HashSize + hashValue];
676b1efbcd6SAlok Aggarwal p->hash[hash2Value] =
677b1efbcd6SAlok Aggarwal p->hash[kFix3HashSize + hashValue] = p->pos;
678b1efbcd6SAlok Aggarwal SKIP_FOOTER
679b1efbcd6SAlok Aggarwal }
680b1efbcd6SAlok Aggarwal while (--num != 0);
681b1efbcd6SAlok Aggarwal }
682b1efbcd6SAlok Aggarwal
Bt4_MatchFinder_Skip(CMatchFinder * p,UInt32 num)683b1efbcd6SAlok Aggarwal static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
684b1efbcd6SAlok Aggarwal {
685b1efbcd6SAlok Aggarwal do
686b1efbcd6SAlok Aggarwal {
687b1efbcd6SAlok Aggarwal UInt32 hash2Value, hash3Value;
688b1efbcd6SAlok Aggarwal SKIP_HEADER(4)
689b1efbcd6SAlok Aggarwal HASH4_CALC;
690b1efbcd6SAlok Aggarwal curMatch = p->hash[kFix4HashSize + hashValue];
691b1efbcd6SAlok Aggarwal p->hash[ hash2Value] =
692b1efbcd6SAlok Aggarwal p->hash[kFix3HashSize + hash3Value] = p->pos;
693b1efbcd6SAlok Aggarwal p->hash[kFix4HashSize + hashValue] = p->pos;
694b1efbcd6SAlok Aggarwal SKIP_FOOTER
695b1efbcd6SAlok Aggarwal }
696b1efbcd6SAlok Aggarwal while (--num != 0);
697b1efbcd6SAlok Aggarwal }
698b1efbcd6SAlok Aggarwal
Hc4_MatchFinder_Skip(CMatchFinder * p,UInt32 num)699b1efbcd6SAlok Aggarwal static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
700b1efbcd6SAlok Aggarwal {
701b1efbcd6SAlok Aggarwal do
702b1efbcd6SAlok Aggarwal {
703b1efbcd6SAlok Aggarwal UInt32 hash2Value, hash3Value;
704b1efbcd6SAlok Aggarwal SKIP_HEADER(4)
705b1efbcd6SAlok Aggarwal HASH4_CALC;
706b1efbcd6SAlok Aggarwal curMatch = p->hash[kFix4HashSize + hashValue];
707b1efbcd6SAlok Aggarwal p->hash[ hash2Value] =
708b1efbcd6SAlok Aggarwal p->hash[kFix3HashSize + hash3Value] =
709b1efbcd6SAlok Aggarwal p->hash[kFix4HashSize + hashValue] = p->pos;
710b1efbcd6SAlok Aggarwal p->son[p->cyclicBufferPos] = curMatch;
711b1efbcd6SAlok Aggarwal MOVE_POS
712b1efbcd6SAlok Aggarwal }
713b1efbcd6SAlok Aggarwal while (--num != 0);
714b1efbcd6SAlok Aggarwal }
715b1efbcd6SAlok Aggarwal
Hc3Zip_MatchFinder_Skip(CMatchFinder * p,UInt32 num)716b1efbcd6SAlok Aggarwal void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
717b1efbcd6SAlok Aggarwal {
718b1efbcd6SAlok Aggarwal do
719b1efbcd6SAlok Aggarwal {
720b1efbcd6SAlok Aggarwal SKIP_HEADER(3)
721b1efbcd6SAlok Aggarwal HASH_ZIP_CALC;
722b1efbcd6SAlok Aggarwal curMatch = p->hash[hashValue];
723b1efbcd6SAlok Aggarwal p->hash[hashValue] = p->pos;
724b1efbcd6SAlok Aggarwal p->son[p->cyclicBufferPos] = curMatch;
725b1efbcd6SAlok Aggarwal MOVE_POS
726b1efbcd6SAlok Aggarwal }
727b1efbcd6SAlok Aggarwal while (--num != 0);
728b1efbcd6SAlok Aggarwal }
729b1efbcd6SAlok Aggarwal
MatchFinder_CreateVTable(CMatchFinder * p,IMatchFinder * vTable)730b1efbcd6SAlok Aggarwal void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
731b1efbcd6SAlok Aggarwal {
732b1efbcd6SAlok Aggarwal vTable->Init = (Mf_Init_Func)MatchFinder_Init;
733b1efbcd6SAlok Aggarwal vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
734b1efbcd6SAlok Aggarwal vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
735b1efbcd6SAlok Aggarwal vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
736b1efbcd6SAlok Aggarwal if (!p->btMode)
737b1efbcd6SAlok Aggarwal {
738b1efbcd6SAlok Aggarwal vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
739b1efbcd6SAlok Aggarwal vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
740b1efbcd6SAlok Aggarwal }
741b1efbcd6SAlok Aggarwal else if (p->numHashBytes == 2)
742b1efbcd6SAlok Aggarwal {
743b1efbcd6SAlok Aggarwal vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
744b1efbcd6SAlok Aggarwal vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
745b1efbcd6SAlok Aggarwal }
746b1efbcd6SAlok Aggarwal else if (p->numHashBytes == 3)
747b1efbcd6SAlok Aggarwal {
748b1efbcd6SAlok Aggarwal vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
749b1efbcd6SAlok Aggarwal vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
750b1efbcd6SAlok Aggarwal }
751b1efbcd6SAlok Aggarwal else
752b1efbcd6SAlok Aggarwal {
753b1efbcd6SAlok Aggarwal vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
754b1efbcd6SAlok Aggarwal vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
755b1efbcd6SAlok Aggarwal }
756b1efbcd6SAlok Aggarwal }
757