← Back to branch summary

~ubuntu-branches/ubuntu/precise/p7zip/precise-updates

« back to all changes in this revision

Viewing changes to C/LzFind.c

  • Committer: Bazaar Package Importer
  • Author(s): Mohammed Adnène Trojette
  • Date: 2009-02-14 20:12:27 UTC
  • mfrom: (1.1.11 upstream) (2.1.3 sid)
  • Revision ID: james.westby@ubuntu.com-20090214201227-go63qxm9ozfdma60
Tags: 4.65~dfsg.1-1
* New upstream release.
* Remove wx2.8 Build-Depends added by mistakes (7zG is not yet
  intended to be built).
* Use dh_clean without -k.

Show diffs side-by-side

added added

removed removed

Lines of Context:
C/LzFind.c
1
 
/* LzFind.c  -- Match finder for LZ algorithms
2
 
2008-04-04
3
 
Copyright (c) 1999-2008 Igor Pavlov
4
 
Read LzFind.h for license options */
 
1
/* LzFind.c -- Match finder for LZ algorithms
 
2
2008-10-04 : Igor Pavlov : Public domain */
5
3
 
6
4
#include <string.h>
7
5
 
82
80
 
83
81
void MatchFinder_MoveBlock(CMatchFinder *p)
84
82
{
85
 
  memmove(p->bufferBase, 
86
 
    p->buffer - p->keepSizeBefore, 
 
83
  memmove(p->bufferBase,
 
84
    p->buffer - p->keepSizeBefore,
87
85
    (size_t)(p->streamPos - p->pos + p->keepSizeBefore));
88
86
  p->buffer = p->bufferBase + p->keepSizeBefore;
89
87
}
96
94
 
97
95
void MatchFinder_ReadIfRequired(CMatchFinder *p)
98
96
{
99
 
  if (p->streamEndWasReached) 
 
97
  if (p->streamEndWasReached)
100
98
    return;
101
99
  if (p->keepSizeAfter >= p->streamPos - p->pos)
102
100
    MatchFinder_ReadBlock(p);
159
157
  return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
160
158
}
161
159
 
162
 
int MatchFinder_Create(CMatchFinder *p, UInt32 historySize, 
 
160
int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
163
161
    UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
164
162
    ISzAlloc *alloc)
165
163
{
174
172
    sizeReserv = historySize >> 2;
175
173
  sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
176
174
 
177
 
  p->keepSizeBefore = historySize + keepAddBufferBefore + 1; 
 
175
  p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
178
176
  p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
179
177
  /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
180
178
  if (LzInWindow_Create(p, sizeReserv, alloc))
239
237
{
240
238
  UInt32 limit = kMaxValForNormalize - p->pos;
241
239
  UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
242
 
  if (limit2 < limit) 
 
240
  if (limit2 < limit)
243
241
    limit = limit2;
244
242
  limit2 = p->streamPos - p->pos;
245
243
  if (limit2 <= p->keepSizeAfter)
249
247
  }
250
248
  else
251
249
    limit2 -= p->keepSizeAfter;
252
 
  if (limit2 < limit) 
 
250
  if (limit2 < limit)
253
251
    limit = limit2;
254
252
  {
255
253
    UInt32 lenLimit = p->streamPos - p->pos;
263
261
void MatchFinder_Init(CMatchFinder *p)
264
262
{
265
263
  UInt32 i;
266
 
  for(i = 0; i < p->hashSizeSum; i++)
 
264
  for (i = 0; i < p->hashSizeSum; i++)
267
265
    p->hash[i] = kEmptyHashValue;
268
266
  p->cyclicBufferPos = 0;
269
267
  p->buffer = p->bufferBase;
274
272
  MatchFinder_SetLimits(p);
275
273
}
276
274
 
277
 
static UInt32 MatchFinder_GetSubValue(CMatchFinder *p) 
278
 
{ 
279
 
  return (p->pos - p->historySize - 1) & kNormalizeMask; 
 
275
static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
 
276
{
 
277
  return (p->pos - p->historySize - 1) & kNormalizeMask;
280
278
}
281
279
 
282
280
void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
311
309
  MatchFinder_SetLimits(p);
312
310
}
313
311
 
314
 
static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son, 
315
 
    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue, 
 
312
static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 
313
    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
316
314
    UInt32 *distances, UInt32 maxLen)
317
315
{
318
316
  son[_cyclicBufferPos] = curMatch;
327
325
      if (pb[maxLen] == cur[maxLen] && *pb == *cur)
328
326
      {
329
327
        UInt32 len = 0;
330
 
        while(++len != lenLimit)
 
328
        while (++len != lenLimit)
331
329
          if (pb[len] != cur[len])
332
330
            break;
333
331
        if (maxLen < len)
342
340
  }
343
341
}
344
342
 
345
 
UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son, 
346
 
    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue, 
 
343
UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 
344
    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
347
345
    UInt32 *distances, UInt32 maxLen)
348
346
{
349
347
  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
364
362
      if (pb[len] == cur[len])
365
363
      {
366
364
        if (++len != lenLimit && pb[len] == cur[len])
367
 
          while(++len != lenLimit)
 
365
          while (++len != lenLimit)
368
366
            if (pb[len] != cur[len])
369
367
              break;
370
368
        if (maxLen < len)
397
395
  }
398
396
}
399
397
 
400
 
static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son, 
 
398
static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
401
399
    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
402
400
{
403
401
  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
417
415
      UInt32 len = (len0 < len1 ? len0 : len1);
418
416
      if (pb[len] == cur[len])
419
417
      {
420
 
        while(++len != lenLimit)
 
418
        while (++len != lenLimit)
421
419
          if (pb[len] != cur[len])
422
420
            break;
423
421
        {
505
503
  delta2 = p->pos - p->hash[hash2Value];
506
504
  curMatch = p->hash[kFix3HashSize + hashValue];
507
505
  
508
 
  p->hash[hash2Value] = 
 
506
  p->hash[hash2Value] =
509
507
  p->hash[kFix3HashSize + hashValue] = p->pos;
510
508
 
511
509
 
522
520
    if (maxLen == lenLimit)
523
521
    {
524
522
      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
525
 
      MOVE_POS_RET; 
 
523
      MOVE_POS_RET;
526
524
    }
527
525
  }
528
526
  GET_MATCHES_FOOTER(offset, maxLen)
567
565
    if (maxLen == lenLimit)
568
566
    {
569
567
      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
570
 
      MOVE_POS_RET; 
 
568
      MOVE_POS_RET;
571
569
    }
572
570
  }
573
571
  if (maxLen < 3)
614
612
    if (maxLen == lenLimit)
615
613
    {
616
614
      p->son[p->cyclicBufferPos] = curMatch;
617
 
      MOVE_POS_RET; 
 
615
      MOVE_POS_RET;
618
616
    }
619
617
  }
620
618
  if (maxLen < 3)
640
638
{
641
639
  do
642
640
  {
643
 
    SKIP_HEADER(2) 
 
641
    SKIP_HEADER(2)
644
642
    HASH2_CALC;
645
643
    curMatch = p->hash[hashValue];
646
644
    p->hash[hashValue] = p->pos;
682
680
  do
683
681
  {
684
682
    UInt32 hash2Value, hash3Value;
685
 
    SKIP_HEADER(4) 
 
683
    SKIP_HEADER(4)
686
684
    HASH4_CALC;
687
685
    curMatch = p->hash[kFix4HashSize + hashValue];
688
686
    p->hash[                hash2Value] =