← Back to branch summary

~darkmuggle-deactivatedaccount/ubuntu/quantal/grub2/fix-872244

« back to all changes in this revision

Viewing changes to lib/LzFind.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson, Colin Watson, Evan Broder, Mario Limonciello
  • Date: 2010-11-24 13:59:55 UTC
  • mfrom: (1.17.6 upstream) (17.6.15 experimental)
  • Revision ID: james.westby@ubuntu.com-20101124135955-r6ii5sepayr7jt53
Tags: 1.99~20101124-1ubuntu1
https://launchpad.net/bugs/677758
[ Colin Watson ]
* Resynchronise with Debian experimental.  Remaining changes:
  - Adjust for default Ubuntu boot options ("quiet splash").
  - Default to hiding the menu; holding down Shift at boot will show it.
  - Set a monochromatic theme for Ubuntu.
  - Apply Ubuntu GRUB Legacy changes to legacy update-grub script: title,
    recovery mode, quiet option, tweak how memtest86+ is displayed, and
    use UUIDs where appropriate.
  - Fix backslash-escaping in merge_debconf_into_conf.
  - Remove "GNU/Linux" from default distributor string.
  - Add crashkernel= options if kdump and makedumpfile are available.
  - If other operating systems are installed, then automatically unhide
    the menu.  Otherwise, if GRUB_HIDDEN_TIMEOUT is 0, then use keystatus
    if available to check whether Shift is pressed.  If it is, show the
    menu, otherwise boot immediately.  If keystatus is not available, then
    fall back to a short delay interruptible with Escape.
  - Allow Shift to interrupt 'sleep --interruptible'.
  - Don't display introductory message about line editing unless we're
    actually offering a shell prompt.  Don't clear the screen just before
    booting if we never drew the menu in the first place.
  - Remove some verbose messages printed before reading the configuration
    file.
  - Suppress progress messages as the kernel and initrd load for
    non-recovery kernel menu entries.
  - Change prepare_grub_to_access_device to handle filesystems
    loop-mounted on file images.
  - Ignore devices loop-mounted from files in 10_linux.
  - Show the boot menu if the previous boot failed, that is if it failed
    to get to the end of one of the normal runlevels.
  - Don't generate /boot/grub/device.map during grub-install or
    grub-mkconfig by default.
  - Adjust upgrade version checks for Ubuntu.
  - Don't display "GRUB loading" unless Shift is held down.
  - Adjust versions of grub-doc and grub-legacy-doc conflicts to tolerate
    our backport of the grub-doc split.
  - Fix LVM/RAID probing in the absence of /boot/grub/device.map.
  - Look for .mo files in /usr/share/locale-langpack as well, in
    preference.
  - Make sure GRUB_TIMEOUT isn't quoted unnecessarily.
  - Probe all devices in 'grub-probe --target=drive' if
    /boot/grub/device.map is missing.
  - Build-depend on qemu-kvm rather than qemu-system for grub-pc tests.
  - Use qemu rather than qemu-system-i386.
  - Program vesafb on BIOS systems rather than efifb.
  - Add a grub-rescue-efi-amd64 package containing a rescue CD-ROM image
    for EFI-AMD64.
  - On Wubi, don't ask for an install device, but just update wubildr
    using the diverted grub-install.
  - When embedding the core image in a post-MBR gap, check for and avoid
    sectors matching any of a list of known signatures.
  - Disable video_bochs and video_cirrus on PC BIOS systems, as probing
    PCI space seems to break on some systems.
* Downgrade "ACPI shutdown failed" error to a debug message, since it can
  cause spurious test failures.

[ Evan Broder ]
* Enable lua from grub-extras.
* Incorporate the bitop library into lua.
* Add enum_pci function to grub module in lua.
* Switch back to gfxpayload=keep by default, unless the video hardware
  is known to not support it.

[ Mario Limonciello ]
* Built part_msdos and vfat into bootx64.efi (LP: #677758)

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
 
}