Mercurial > vba-linux

     1 /* LzFind.c -- Match finder for LZ algorithms

     2 2008-10-04 : Igor Pavlov : Public domain */

     3 

     4 #include <string.h>

     5 

     6 #include "LzFind.h"

     7 #include "LzHash.h"

     8 

     9 #define kEmptyHashValue 0

    10 #define kMaxValForNormalize ((UInt32)0xFFFFFFFF)

    11 #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */

    12 #define kNormalizeMask (~(kNormalizeStepMin - 1))

    13 #define kMaxHistorySize ((UInt32)3 << 30)

    14 

    15 #define kStartMaxLen 3

    16 

    17 static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)

    18 {

    19   if (!p->directInput)

    20   {

    21     alloc->Free(alloc, p->bufferBase);

    22     p->bufferBase = 0;

    23   }

    24 }

    25 

    26 /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */

    27 

    28 static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)

    29 {

    30   UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;

    31   if (p->directInput)

    32   {

    33     p->blockSize = blockSize;

    34     return 1;

    35   }

    36   if (p->bufferBase == 0 || p->blockSize != blockSize)

    37   {

    38     LzInWindow_Free(p, alloc);

    39     p->blockSize = blockSize;

    40     p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);

    41   }

    42   return (p->bufferBase != 0);

    43 }

    44 

    45 Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }

    46 Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[index]; }

    47 

    48 UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }

    49 

    50 void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)

    51 {

    52   p->posLimit -= subValue;

    53   p->pos -= subValue;

    54   p->streamPos -= subValue;

    55 }

    56 

    57 static void MatchFinder_ReadBlock(CMatchFinder *p)

    58 {

    59   if (p->streamEndWasReached || p->result != SZ_OK)

    60     return;

    61   for (;;)

    62   {

    63     Byte *dest = p->buffer + (p->streamPos - p->pos);

    64     size_t size = (p->bufferBase + p->blockSize - dest);

    65     if (size == 0)

    66       return;

    67     p->result = p->stream->Read(p->stream, dest, &size);

    68     if (p->result != SZ_OK)

    69       return;

    70     if (size == 0)

    71     {

    72       p->streamEndWasReached = 1;

    73       return;

    74     }

    75     p->streamPos += (UInt32)size;

    76     if (p->streamPos - p->pos > p->keepSizeAfter)

    77       return;

    78   }

    79 }

    80 

    81 void MatchFinder_MoveBlock(CMatchFinder *p)

    82 {

    83   memmove(p->bufferBase,

    84     p->buffer - p->keepSizeBefore,

    85     (size_t)(p->streamPos - p->pos + p->keepSizeBefore));

    86   p->buffer = p->bufferBase + p->keepSizeBefore;

    87 }

    88 

    89 int MatchFinder_NeedMove(CMatchFinder *p)

    90 {

    91   /* if (p->streamEndWasReached) return 0; */

    92   return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);

    93 }

    94 

    95 void MatchFinder_ReadIfRequired(CMatchFinder *p)

    96 {

    97   if (p->streamEndWasReached)

    98     return;

    99   if (p->keepSizeAfter >= p->streamPos - p->pos)

   100     MatchFinder_ReadBlock(p);

   101 }

   102 

   103 static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)

   104 {

   105   if (MatchFinder_NeedMove(p))

   106     MatchFinder_MoveBlock(p);

   107   MatchFinder_ReadBlock(p);

   108 }

   109 

   110 static void MatchFinder_SetDefaultSettings(CMatchFinder *p)

   111 {

   112   p->cutValue = 32;

   113   p->btMode = 1;

   114   p->numHashBytes = 4;

   115   /* p->skipModeBits = 0; */

   116   p->directInput = 0;

   117   p->bigHash = 0;

   118 }

   119 

   120 #define kCrcPoly 0xEDB88320

   121 

   122 void MatchFinder_Construct(CMatchFinder *p)

   123 {

   124   UInt32 i;

   125   p->bufferBase = 0;

   126   p->directInput = 0;

   127   p->hash = 0;

   128   MatchFinder_SetDefaultSettings(p);

   129 

   130   for (i = 0; i < 256; i++)

   131   {

   132     UInt32 r = i;

   133     int j;

   134     for (j = 0; j < 8; j++)

   135       r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));

   136     p->crc[i] = r;

   137   }

   138 }

   139 

   140 static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)

   141 {

   142   alloc->Free(alloc, p->hash);

   143   p->hash = 0;

   144 }

   145 

   146 void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)

   147 {

   148   MatchFinder_FreeThisClassMemory(p, alloc);

   149   LzInWindow_Free(p, alloc);

   150 }

   151 

   152 static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)

   153 {

   154   size_t sizeInBytes = (size_t)num * sizeof(CLzRef);

   155   if (sizeInBytes / sizeof(CLzRef) != num)

   156     return 0;

   157   return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);

   158 }

   159 

   160 int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,

   161     UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,

   162     ISzAlloc *alloc)

   163 {

   164   UInt32 sizeReserv;

   165   if (historySize > kMaxHistorySize)

   166   {

   167     MatchFinder_Free(p, alloc);

   168     return 0;

   169   }

   170   sizeReserv = historySize >> 1;

   171   if (historySize > ((UInt32)2 << 30))

   172     sizeReserv = historySize >> 2;

   173   sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);

   174 

   175   p->keepSizeBefore = historySize + keepAddBufferBefore + 1;

   176   p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;

   177   /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */

   178   if (LzInWindow_Create(p, sizeReserv, alloc))

   179   {

   180     UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;

   181     UInt32 hs;

   182     p->matchMaxLen = matchMaxLen;

   183     {

   184       p->fixedHashSize = 0;

   185       if (p->numHashBytes == 2)

   186         hs = (1 << 16) - 1;

   187       else

   188       {

   189         hs = historySize - 1;

   190         hs |= (hs >> 1);

   191         hs |= (hs >> 2);

   192         hs |= (hs >> 4);

   193         hs |= (hs >> 8);

   194         hs >>= 1;

   195         /* hs >>= p->skipModeBits; */

   196         hs |= 0xFFFF; /* don't change it! It's required for Deflate */

   197         if (hs > (1 << 24))

   198         {

   199           if (p->numHashBytes == 3)

   200             hs = (1 << 24) - 1;

   201           else

   202             hs >>= 1;

   203         }

   204       }

   205       p->hashMask = hs;

   206       hs++;

   207       if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;

   208       if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;

   209       if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;

   210       hs += p->fixedHashSize;

   211     }

   212 

   213     {

   214       UInt32 prevSize = p->hashSizeSum + p->numSons;

   215       UInt32 newSize;

   216       p->historySize = historySize;

   217       p->hashSizeSum = hs;

   218       p->cyclicBufferSize = newCyclicBufferSize;

   219       p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);

   220       newSize = p->hashSizeSum + p->numSons;

   221       if (p->hash != 0 && prevSize == newSize)

   222         return 1;

   223       MatchFinder_FreeThisClassMemory(p, alloc);

   224       p->hash = AllocRefs(newSize, alloc);

   225       if (p->hash != 0)

   226       {

   227         p->son = p->hash + p->hashSizeSum;

   228         return 1;

   229       }

   230     }

   231   }

   232   MatchFinder_Free(p, alloc);

   233   return 0;

   234 }

   235 

   236 static void MatchFinder_SetLimits(CMatchFinder *p)

   237 {

   238   UInt32 limit = kMaxValForNormalize - p->pos;

   239   UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;

   240   if (limit2 < limit)

   241     limit = limit2;

   242   limit2 = p->streamPos - p->pos;

   243   if (limit2 <= p->keepSizeAfter)

   244   {

   245     if (limit2 > 0)

   246       limit2 = 1;

   247   }

   248   else

   249     limit2 -= p->keepSizeAfter;

   250   if (limit2 < limit)

   251     limit = limit2;

   252   {

   253     UInt32 lenLimit = p->streamPos - p->pos;

   254     if (lenLimit > p->matchMaxLen)

   255       lenLimit = p->matchMaxLen;

   256     p->lenLimit = lenLimit;

   257   }

   258   p->posLimit = p->pos + limit;

   259 }

   260 

   261 void MatchFinder_Init(CMatchFinder *p)

   262 {

   263   UInt32 i;

   264   for (i = 0; i < p->hashSizeSum; i++)

   265     p->hash[i] = kEmptyHashValue;

   266   p->cyclicBufferPos = 0;

   267   p->buffer = p->bufferBase;

   268   p->pos = p->streamPos = p->cyclicBufferSize;

   269   p->result = SZ_OK;

   270   p->streamEndWasReached = 0;

   271   MatchFinder_ReadBlock(p);

   272   MatchFinder_SetLimits(p);

   273 }

   274 

   275 static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)

   276 {

   277   return (p->pos - p->historySize - 1) & kNormalizeMask;

   278 }

   279 

   280 void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)

   281 {

   282   UInt32 i;

   283   for (i = 0; i < numItems; i++)

   284   {

   285     UInt32 value = items[i];

   286     if (value <= subValue)

   287       value = kEmptyHashValue;

   288     else

   289       value -= subValue;

   290     items[i] = value;

   291   }

   292 }

   293 

   294 static void MatchFinder_Normalize(CMatchFinder *p)

   295 {

   296   UInt32 subValue = MatchFinder_GetSubValue(p);

   297   MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);

   298   MatchFinder_ReduceOffsets(p, subValue);

   299 }

   300 

   301 static void MatchFinder_CheckLimits(CMatchFinder *p)

   302 {

   303   if (p->pos == kMaxValForNormalize)

   304     MatchFinder_Normalize(p);

   305   if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)

   306     MatchFinder_CheckAndMoveAndRead(p);

   307   if (p->cyclicBufferPos == p->cyclicBufferSize)

   308     p->cyclicBufferPos = 0;

   309   MatchFinder_SetLimits(p);

   310 }

   311 

   312 static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,

   313     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,

   314     UInt32 *distances, UInt32 maxLen)

   315 {

   316   son[_cyclicBufferPos] = curMatch;

   317   for (;;)

   318   {

   319     UInt32 delta = pos - curMatch;

   320     if (cutValue-- == 0 || delta >= _cyclicBufferSize)

   321       return distances;

   322     {

   323       const Byte *pb = cur - delta;

   324       curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];

   325       if (pb[maxLen] == cur[maxLen] && *pb == *cur)

   326       {

   327         UInt32 len = 0;

   328         while (++len != lenLimit)

   329           if (pb[len] != cur[len])

   330             break;

   331         if (maxLen < len)

   332         {

   333           *distances++ = maxLen = len;

   334           *distances++ = delta - 1;

   335           if (len == lenLimit)

   336             return distances;

   337         }

   338       }

   339     }

   340   }

   341 }

   342 

   343 UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,

   344     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,

   345     UInt32 *distances, UInt32 maxLen)

   346 {

   347   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;

   348   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);

   349   UInt32 len0 = 0, len1 = 0;

   350   for (;;)

   351   {

   352     UInt32 delta = pos - curMatch;

   353     if (cutValue-- == 0 || delta >= _cyclicBufferSize)

   354     {

   355       *ptr0 = *ptr1 = kEmptyHashValue;

   356       return distances;

   357     }

   358     {

   359       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);

   360       const Byte *pb = cur - delta;

   361       UInt32 len = (len0 < len1 ? len0 : len1);

   362       if (pb[len] == cur[len])

   363       {

   364         if (++len != lenLimit && pb[len] == cur[len])

   365           while (++len != lenLimit)

   366             if (pb[len] != cur[len])

   367               break;

   368         if (maxLen < len)

   369         {

   370           *distances++ = maxLen = len;

   371           *distances++ = delta - 1;

   372           if (len == lenLimit)

   373           {

   374             *ptr1 = pair[0];

   375             *ptr0 = pair[1];

   376             return distances;

   377           }

   378         }

   379       }

   380       if (pb[len] < cur[len])

   381       {

   382         *ptr1 = curMatch;

   383         ptr1 = pair + 1;

   384         curMatch = *ptr1;

   385         len1 = len;

   386       }

   387       else

   388       {

   389         *ptr0 = curMatch;

   390         ptr0 = pair;

   391         curMatch = *ptr0;

   392         len0 = len;

   393       }

   394     }

   395   }

   396 }

   397 

   398 static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,

   399     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)

   400 {

   401   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;

   402   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);

   403   UInt32 len0 = 0, len1 = 0;

   404   for (;;)

   405   {

   406     UInt32 delta = pos - curMatch;

   407     if (cutValue-- == 0 || delta >= _cyclicBufferSize)

   408     {

   409       *ptr0 = *ptr1 = kEmptyHashValue;

   410       return;

   411     }

   412     {

   413       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);

   414       const Byte *pb = cur - delta;

   415       UInt32 len = (len0 < len1 ? len0 : len1);

   416       if (pb[len] == cur[len])

   417       {

   418         while (++len != lenLimit)

   419           if (pb[len] != cur[len])

   420             break;

   421         {

   422           if (len == lenLimit)

   423           {

   424             *ptr1 = pair[0];

   425             *ptr0 = pair[1];

   426             return;

   427           }

   428         }

   429       }

   430       if (pb[len] < cur[len])

   431       {

   432         *ptr1 = curMatch;

   433         ptr1 = pair + 1;

   434         curMatch = *ptr1;

   435         len1 = len;

   436       }

   437       else

   438       {

   439         *ptr0 = curMatch;

   440         ptr0 = pair;

   441         curMatch = *ptr0;

   442         len0 = len;

   443       }

   444     }

   445   }

   446 }

   447 

   448 #define MOVE_POS \

   449   ++p->cyclicBufferPos; \

   450   p->buffer++; \

   451   if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);

   452 

   453 #define MOVE_POS_RET MOVE_POS return offset;

   454 

   455 static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }

   456 

   457 #define GET_MATCHES_HEADER2(minLen, ret_op) \

   458   UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \

   459   lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \

   460   cur = p->buffer;

   461 

   462 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)

   463 #define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)

   464 

   465 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue

   466 

   467 #define GET_MATCHES_FOOTER(offset, maxLen) \

   468   offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \

   469   distances + offset, maxLen) - distances); MOVE_POS_RET;

   470 

   471 #define SKIP_FOOTER \

   472   SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;

   473 

   474 static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

   475 {

   476   UInt32 offset;

   477   GET_MATCHES_HEADER(2)

   478   HASH2_CALC;

   479   curMatch = p->hash[hashValue];

   480   p->hash[hashValue] = p->pos;

   481   offset = 0;

   482   GET_MATCHES_FOOTER(offset, 1)

   483 }

   484 

   485 UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

   486 {

   487   UInt32 offset;

   488   GET_MATCHES_HEADER(3)

   489   HASH_ZIP_CALC;

   490   curMatch = p->hash[hashValue];

   491   p->hash[hashValue] = p->pos;

   492   offset = 0;

   493   GET_MATCHES_FOOTER(offset, 2)

   494 }

   495 

   496 static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

   497 {

   498   UInt32 hash2Value, delta2, maxLen, offset;

   499   GET_MATCHES_HEADER(3)

   500 

   501   HASH3_CALC;

   502 

   503   delta2 = p->pos - p->hash[hash2Value];

   504   curMatch = p->hash[kFix3HashSize + hashValue];

   505   

   506   p->hash[hash2Value] =

   507   p->hash[kFix3HashSize + hashValue] = p->pos;

   508 

   509 

   510   maxLen = 2;

   511   offset = 0;

   512   if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)

   513   {

   514     for (; maxLen != lenLimit; maxLen++)

   515       if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])

   516         break;

   517     distances[0] = maxLen;

   518     distances[1] = delta2 - 1;

   519     offset = 2;

   520     if (maxLen == lenLimit)

   521     {

   522       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));

   523       MOVE_POS_RET;

   524     }

   525   }

   526   GET_MATCHES_FOOTER(offset, maxLen)

   527 }

   528 

   529 static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

   530 {

   531   UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;

   532   GET_MATCHES_HEADER(4)

   533 

   534   HASH4_CALC;

   535 

   536   delta2 = p->pos - p->hash[                hash2Value];

   537   delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];

   538   curMatch = p->hash[kFix4HashSize + hashValue];

   539   

   540   p->hash[                hash2Value] =

   541   p->hash[kFix3HashSize + hash3Value] =

   542   p->hash[kFix4HashSize + hashValue] = p->pos;

   543 

   544   maxLen = 1;

   545   offset = 0;

   546   if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)

   547   {

   548     distances[0] = maxLen = 2;

   549     distances[1] = delta2 - 1;

   550     offset = 2;

   551   }

   552   if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)

   553   {

   554     maxLen = 3;

   555     distances[offset + 1] = delta3 - 1;

   556     offset += 2;

   557     delta2 = delta3;

   558   }

   559   if (offset != 0)

   560   {

   561     for (; maxLen != lenLimit; maxLen++)

   562       if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])

   563         break;

   564     distances[offset - 2] = maxLen;

   565     if (maxLen == lenLimit)

   566     {

   567       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));

   568       MOVE_POS_RET;

   569     }

   570   }

   571   if (maxLen < 3)

   572     maxLen = 3;

   573   GET_MATCHES_FOOTER(offset, maxLen)

   574 }

   575 

   576 static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

   577 {

   578   UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;

   579   GET_MATCHES_HEADER(4)

   580 

   581   HASH4_CALC;

   582 

   583   delta2 = p->pos - p->hash[                hash2Value];

   584   delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];

   585   curMatch = p->hash[kFix4HashSize + hashValue];

   586 

   587   p->hash[                hash2Value] =

   588   p->hash[kFix3HashSize + hash3Value] =

   589   p->hash[kFix4HashSize + hashValue] = p->pos;

   590 

   591   maxLen = 1;

   592   offset = 0;

   593   if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)

   594   {

   595     distances[0] = maxLen = 2;

   596     distances[1] = delta2 - 1;

   597     offset = 2;

   598   }

   599   if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)

   600   {

   601     maxLen = 3;

   602     distances[offset + 1] = delta3 - 1;

   603     offset += 2;

   604     delta2 = delta3;

   605   }

   606   if (offset != 0)

   607   {

   608     for (; maxLen != lenLimit; maxLen++)

   609       if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])

   610         break;

   611     distances[offset - 2] = maxLen;

   612     if (maxLen == lenLimit)

   613     {

   614       p->son[p->cyclicBufferPos] = curMatch;

   615       MOVE_POS_RET;

   616     }

   617   }

   618   if (maxLen < 3)

   619     maxLen = 3;

   620   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),

   621     distances + offset, maxLen) - (distances));

   622   MOVE_POS_RET

   623 }

   624 

   625 UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

   626 {

   627   UInt32 offset;

   628   GET_MATCHES_HEADER(3)

   629   HASH_ZIP_CALC;

   630   curMatch = p->hash[hashValue];

   631   p->hash[hashValue] = p->pos;

   632   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),

   633     distances, 2) - (distances));

   634   MOVE_POS_RET

   635 }

   636 

   637 static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

   638 {

   639   do

   640   {

   641     SKIP_HEADER(2)

   642     HASH2_CALC;

   643     curMatch = p->hash[hashValue];

   644     p->hash[hashValue] = p->pos;

   645     SKIP_FOOTER

   646   }

   647   while (--num != 0);

   648 }

   649 

   650 void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

   651 {

   652   do

   653   {

   654     SKIP_HEADER(3)

   655     HASH_ZIP_CALC;

   656     curMatch = p->hash[hashValue];

   657     p->hash[hashValue] = p->pos;

   658     SKIP_FOOTER

   659   }

   660   while (--num != 0);

   661 }

   662 

   663 static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

   664 {

   665   do

   666   {

   667     UInt32 hash2Value;

   668     SKIP_HEADER(3)

   669     HASH3_CALC;

   670     curMatch = p->hash[kFix3HashSize + hashValue];

   671     p->hash[hash2Value] =

   672     p->hash[kFix3HashSize + hashValue] = p->pos;

   673     SKIP_FOOTER

   674   }

   675   while (--num != 0);

   676 }

   677 

   678 static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

   679 {

   680   do

   681   {

   682     UInt32 hash2Value, hash3Value;

   683     SKIP_HEADER(4)

   684     HASH4_CALC;

   685     curMatch = p->hash[kFix4HashSize + hashValue];

   686     p->hash[                hash2Value] =

   687     p->hash[kFix3HashSize + hash3Value] = p->pos;

   688     p->hash[kFix4HashSize + hashValue] = p->pos;

   689     SKIP_FOOTER

   690   }

   691   while (--num != 0);

   692 }

   693 

   694 static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

   695 {

   696   do

   697   {

   698     UInt32 hash2Value, hash3Value;

   699     SKIP_HEADER(4)

   700     HASH4_CALC;

   701     curMatch = p->hash[kFix4HashSize + hashValue];

   702     p->hash[                hash2Value] =

   703     p->hash[kFix3HashSize + hash3Value] =

   704     p->hash[kFix4HashSize + hashValue] = p->pos;

   705     p->son[p->cyclicBufferPos] = curMatch;

   706     MOVE_POS

   707   }

   708   while (--num != 0);

   709 }

   710 

   711 void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

   712 {

   713   do

   714   {

   715     SKIP_HEADER(3)

   716     HASH_ZIP_CALC;

   717     curMatch = p->hash[hashValue];

   718     p->hash[hashValue] = p->pos;

   719     p->son[p->cyclicBufferPos] = curMatch;

   720     MOVE_POS

   721   }

   722   while (--num != 0);

   723 }

   724 

   725 void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)

   726 {

   727   vTable->Init = (Mf_Init_Func)MatchFinder_Init;

   728   vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;

   729   vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;

   730   vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;

   731   if (!p->btMode)

   732   {

   733     vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;

   734     vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;

   735   }

   736   else if (p->numHashBytes == 2)

   737   {

   738     vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;

   739     vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;

   740   }

   741   else if (p->numHashBytes == 3)

   742   {

   743     vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;

   744     vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;

   745   }

   746   else

   747   {

   748     vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;

   749     vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;

   750   }

   751 }
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 03 Mar 2012 10:31:47 -0600
parents	f9f4f1b99eed
children