← Back to branch summary

~ubuntu-branches/ubuntu/trusty/grub2/trusty-updates

« back to all changes in this revision

Viewing changes to grub-core/lib/LzFind.c

Tags: upstream-1.99~20101122
Import upstream version 1.99~20101122

Show diffs side-by-side

added added

removed removed

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