← Back to branch summary

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

« back to all changes in this revision

Viewing changes to grub-core/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:
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
}