← Back to branch summary

~hamo/ubuntu/precise/grub2/grub2.hi_res

« back to all changes in this revision

Viewing changes to lib/LzFind.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson, Colin Watson, Robert Millan, Updated translations
  • Date: 2010-11-22 12:24:56 UTC
  • mfrom: (1.26.4 upstream) (17.3.36 sid)
  • mto: (17.3.43 sid)
  • mto: This revision was merged to the branch mainline in revision 89.
  • Revision ID: james.westby@ubuntu.com-20101122122456-y82z3sfb7k4zfdcc
Tags: 1.99~20101122-1
http://bugs.debian.org/550658
http://bugs.debian.org/550702
http://bugs.debian.org/591416
http://bugs.debian.org/593347
http://bugs.debian.org/551627
http://bugs.debian.org/589325
http://bugs.debian.org/543924
http://bugs.debian.org/603354
http://bugs.debian.org/604003
http://bugs.debian.org/604102
[ Colin Watson ]
* New Bazaar snapshot.  Too many changes to list in full, but some of the
  more user-visible ones are as follows:
  - GRUB script:
    + Function parameters, "break", "continue", "shift", "setparams",
      "return", and "!".
    + "export" command supports multiple variable names.
    + Multi-line quoted strings support.
    + Wildcard expansion.
  - sendkey support.
  - USB hotunplugging and USB serial support.
  - Rename CD-ROM to cd on BIOS.
  - Add new --boot-directory option to grub-install, grub-reboot, and
    grub-set-default; the old --root-directory option is still accepted
    but was often confusing.
  - Basic btrfs detection/UUID support (but no file reading yet).
  - bash-completion for utilities.
  - If a device is listed in device.map, always assume that it is
    BIOS-visible rather than using extra layers such as LVM or RAID.
  - Add grub-mknetdir script (closes: #550658).
  - Remove deprecated "root" command.
  - Handle RAID devices containing virtio components.
  - GRUB Legacy configuration file support (via grub-menulst2cfg).
  - Keyboard layout support (via grub-mklayout and grub-kbdcomp).
  - Check generated grub.cfg for syntax errors before saving.
  - Pause execution for at most ten seconds if any errors are displayed,
    so that the user has a chance to see them.
  - Support submenus.
  - Write embedding zone using Reed-Solomon, so that it's robust against
    being partially overwritten (closes: #550702, #591416, #593347).
  - GRUB_DISABLE_LINUX_RECOVERY and GRUB_DISABLE_NETBSD_RECOVERY merged
    into a single GRUB_DISABLE_RECOVERY variable.
  - Fix loader memory allocation failure (closes: #551627).
  - Don't call savedefault on recovery entries (closes: #589325).
  - Support triple-indirect blocks on ext2 (closes: #543924).
  - Recognise DDF1 fake RAID (closes: #603354).

[ Robert Millan ]
* Use dpkg architecture wildcards.

[ Updated translations ]
* Slovenian (Vanja Cvelbar).  Closes: #604003
* Dzongkha (dawa pemo via Tenzin Dendup).  Closes: #604102

Show diffs side-by-side

added added

removed removed

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