1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/openctm/liblzma/LzFind.c	Thu Sep 26 04:47:05 2013 +0300
     1.3 @@ -0,0 +1,751 @@
     1.4 +/* LzFind.c -- Match finder for LZ algorithms
     1.5 +2008-10-04 : Igor Pavlov : Public domain */
     1.6 +
     1.7 +#include <string.h>
     1.8 +
     1.9 +#include "LzFind.h"
    1.10 +#include "LzHash.h"
    1.11 +
    1.12 +#define kEmptyHashValue 0
    1.13 +#define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
    1.14 +#define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
    1.15 +#define kNormalizeMask (~(kNormalizeStepMin - 1))
    1.16 +#define kMaxHistorySize ((UInt32)3 << 30)
    1.17 +
    1.18 +#define kStartMaxLen 3
    1.19 +
    1.20 +static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
    1.21 +{
    1.22 +  if (!p->directInput)
    1.23 +  {
    1.24 +    alloc->Free(alloc, p->bufferBase);
    1.25 +    p->bufferBase = 0;
    1.26 +  }
    1.27 +}
    1.28 +
    1.29 +/* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
    1.30 +
    1.31 +static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)
    1.32 +{
    1.33 +  UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
    1.34 +  if (p->directInput)
    1.35 +  {
    1.36 +    p->blockSize = blockSize;
    1.37 +    return 1;
    1.38 +  }
    1.39 +  if (p->bufferBase == 0 || p->blockSize != blockSize)
    1.40 +  {
    1.41 +    LzInWindow_Free(p, alloc);
    1.42 +    p->blockSize = blockSize;
    1.43 +    p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
    1.44 +  }
    1.45 +  return (p->bufferBase != 0);
    1.46 +}
    1.47 +
    1.48 +Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
    1.49 +Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[index]; }
    1.50 +
    1.51 +UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
    1.52 +
    1.53 +void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
    1.54 +{
    1.55 +  p->posLimit -= subValue;
    1.56 +  p->pos -= subValue;
    1.57 +  p->streamPos -= subValue;
    1.58 +}
    1.59 +
    1.60 +static void MatchFinder_ReadBlock(CMatchFinder *p)
    1.61 +{
    1.62 +  if (p->streamEndWasReached || p->result != SZ_OK)
    1.63 +    return;
    1.64 +  for (;;)
    1.65 +  {
    1.66 +    Byte *dest = p->buffer + (p->streamPos - p->pos);
    1.67 +    size_t size = (p->bufferBase + p->blockSize - dest);
    1.68 +    if (size == 0)
    1.69 +      return;
    1.70 +    p->result = p->stream->Read(p->stream, dest, &size);
    1.71 +    if (p->result != SZ_OK)
    1.72 +      return;
    1.73 +    if (size == 0)
    1.74 +    {
    1.75 +      p->streamEndWasReached = 1;
    1.76 +      return;
    1.77 +    }
    1.78 +    p->streamPos += (UInt32)size;
    1.79 +    if (p->streamPos - p->pos > p->keepSizeAfter)
    1.80 +      return;
    1.81 +  }
    1.82 +}
    1.83 +
    1.84 +void MatchFinder_MoveBlock(CMatchFinder *p)
    1.85 +{
    1.86 +  memmove(p->bufferBase,
    1.87 +    p->buffer - p->keepSizeBefore,
    1.88 +    (size_t)(p->streamPos - p->pos + p->keepSizeBefore));
    1.89 +  p->buffer = p->bufferBase + p->keepSizeBefore;
    1.90 +}
    1.91 +
    1.92 +int MatchFinder_NeedMove(CMatchFinder *p)
    1.93 +{
    1.94 +  /* if (p->streamEndWasReached) return 0; */
    1.95 +  return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
    1.96 +}
    1.97 +
    1.98 +void MatchFinder_ReadIfRequired(CMatchFinder *p)
    1.99 +{
   1.100 +  if (p->streamEndWasReached)
   1.101 +    return;
   1.102 +  if (p->keepSizeAfter >= p->streamPos - p->pos)
   1.103 +    MatchFinder_ReadBlock(p);
   1.104 +}
   1.105 +
   1.106 +static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
   1.107 +{
   1.108 +  if (MatchFinder_NeedMove(p))
   1.109 +    MatchFinder_MoveBlock(p);
   1.110 +  MatchFinder_ReadBlock(p);
   1.111 +}
   1.112 +
   1.113 +static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
   1.114 +{
   1.115 +  p->cutValue = 32;
   1.116 +  p->btMode = 1;
   1.117 +  p->numHashBytes = 4;
   1.118 +  /* p->skipModeBits = 0; */
   1.119 +  p->directInput = 0;
   1.120 +  p->bigHash = 0;
   1.121 +}
   1.122 +
   1.123 +#define kCrcPoly 0xEDB88320
   1.124 +
   1.125 +void MatchFinder_Construct(CMatchFinder *p)
   1.126 +{
   1.127 +  UInt32 i;
   1.128 +  p->bufferBase = 0;
   1.129 +  p->directInput = 0;
   1.130 +  p->hash = 0;
   1.131 +  MatchFinder_SetDefaultSettings(p);
   1.132 +
   1.133 +  for (i = 0; i < 256; i++)
   1.134 +  {
   1.135 +    UInt32 r = i;
   1.136 +    int j;
   1.137 +    for (j = 0; j < 8; j++)
   1.138 +      r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
   1.139 +    p->crc[i] = r;
   1.140 +  }
   1.141 +}
   1.142 +
   1.143 +static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
   1.144 +{
   1.145 +  alloc->Free(alloc, p->hash);
   1.146 +  p->hash = 0;
   1.147 +}
   1.148 +
   1.149 +void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
   1.150 +{
   1.151 +  MatchFinder_FreeThisClassMemory(p, alloc);
   1.152 +  LzInWindow_Free(p, alloc);
   1.153 +}
   1.154 +
   1.155 +static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)
   1.156 +{
   1.157 +  size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
   1.158 +  if (sizeInBytes / sizeof(CLzRef) != num)
   1.159 +    return 0;
   1.160 +  return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
   1.161 +}
   1.162 +
   1.163 +int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
   1.164 +    UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
   1.165 +    ISzAlloc *alloc)
   1.166 +{
   1.167 +  UInt32 sizeReserv;
   1.168 +  if (historySize > kMaxHistorySize)
   1.169 +  {
   1.170 +    MatchFinder_Free(p, alloc);
   1.171 +    return 0;
   1.172 +  }
   1.173 +  sizeReserv = historySize >> 1;
   1.174 +  if (historySize > ((UInt32)2 << 30))
   1.175 +    sizeReserv = historySize >> 2;
   1.176 +  sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
   1.177 +
   1.178 +  p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
   1.179 +  p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
   1.180 +  /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
   1.181 +  if (LzInWindow_Create(p, sizeReserv, alloc))
   1.182 +  {
   1.183 +    UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;
   1.184 +    UInt32 hs;
   1.185 +    p->matchMaxLen = matchMaxLen;
   1.186 +    {
   1.187 +      p->fixedHashSize = 0;
   1.188 +      if (p->numHashBytes == 2)
   1.189 +        hs = (1 << 16) - 1;
   1.190 +      else
   1.191 +      {
   1.192 +        hs = historySize - 1;
   1.193 +        hs |= (hs >> 1);
   1.194 +        hs |= (hs >> 2);
   1.195 +        hs |= (hs >> 4);
   1.196 +        hs |= (hs >> 8);
   1.197 +        hs >>= 1;
   1.198 +        /* hs >>= p->skipModeBits; */
   1.199 +        hs |= 0xFFFF; /* don't change it! It's required for Deflate */
   1.200 +        if (hs > (1 << 24))
   1.201 +        {
   1.202 +          if (p->numHashBytes == 3)
   1.203 +            hs = (1 << 24) - 1;
   1.204 +          else
   1.205 +            hs >>= 1;
   1.206 +        }
   1.207 +      }
   1.208 +      p->hashMask = hs;
   1.209 +      hs++;
   1.210 +      if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
   1.211 +      if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
   1.212 +      if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
   1.213 +      hs += p->fixedHashSize;
   1.214 +    }
   1.215 +
   1.216 +    {
   1.217 +      UInt32 prevSize = p->hashSizeSum + p->numSons;
   1.218 +      UInt32 newSize;
   1.219 +      p->historySize = historySize;
   1.220 +      p->hashSizeSum = hs;
   1.221 +      p->cyclicBufferSize = newCyclicBufferSize;
   1.222 +      p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
   1.223 +      newSize = p->hashSizeSum + p->numSons;
   1.224 +      if (p->hash != 0 && prevSize == newSize)
   1.225 +        return 1;
   1.226 +      MatchFinder_FreeThisClassMemory(p, alloc);
   1.227 +      p->hash = AllocRefs(newSize, alloc);
   1.228 +      if (p->hash != 0)
   1.229 +      {
   1.230 +        p->son = p->hash + p->hashSizeSum;
   1.231 +        return 1;
   1.232 +      }
   1.233 +    }
   1.234 +  }
   1.235 +  MatchFinder_Free(p, alloc);
   1.236 +  return 0;
   1.237 +}
   1.238 +
   1.239 +static void MatchFinder_SetLimits(CMatchFinder *p)
   1.240 +{
   1.241 +  UInt32 limit = kMaxValForNormalize - p->pos;
   1.242 +  UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
   1.243 +  if (limit2 < limit)
   1.244 +    limit = limit2;
   1.245 +  limit2 = p->streamPos - p->pos;
   1.246 +  if (limit2 <= p->keepSizeAfter)
   1.247 +  {
   1.248 +    if (limit2 > 0)
   1.249 +      limit2 = 1;
   1.250 +  }
   1.251 +  else
   1.252 +    limit2 -= p->keepSizeAfter;
   1.253 +  if (limit2 < limit)
   1.254 +    limit = limit2;
   1.255 +  {
   1.256 +    UInt32 lenLimit = p->streamPos - p->pos;
   1.257 +    if (lenLimit > p->matchMaxLen)
   1.258 +      lenLimit = p->matchMaxLen;
   1.259 +    p->lenLimit = lenLimit;
   1.260 +  }
   1.261 +  p->posLimit = p->pos + limit;
   1.262 +}
   1.263 +
   1.264 +void MatchFinder_Init(CMatchFinder *p)
   1.265 +{
   1.266 +  UInt32 i;
   1.267 +  for (i = 0; i < p->hashSizeSum; i++)
   1.268 +    p->hash[i] = kEmptyHashValue;
   1.269 +  p->cyclicBufferPos = 0;
   1.270 +  p->buffer = p->bufferBase;
   1.271 +  p->pos = p->streamPos = p->cyclicBufferSize;
   1.272 +  p->result = SZ_OK;
   1.273 +  p->streamEndWasReached = 0;
   1.274 +  MatchFinder_ReadBlock(p);
   1.275 +  MatchFinder_SetLimits(p);
   1.276 +}
   1.277 +
   1.278 +static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
   1.279 +{
   1.280 +  return (p->pos - p->historySize - 1) & kNormalizeMask;
   1.281 +}
   1.282 +
   1.283 +void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
   1.284 +{
   1.285 +  UInt32 i;
   1.286 +  for (i = 0; i < numItems; i++)
   1.287 +  {
   1.288 +    UInt32 value = items[i];
   1.289 +    if (value <= subValue)
   1.290 +      value = kEmptyHashValue;
   1.291 +    else
   1.292 +      value -= subValue;
   1.293 +    items[i] = value;
   1.294 +  }
   1.295 +}
   1.296 +
   1.297 +static void MatchFinder_Normalize(CMatchFinder *p)
   1.298 +{
   1.299 +  UInt32 subValue = MatchFinder_GetSubValue(p);
   1.300 +  MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
   1.301 +  MatchFinder_ReduceOffsets(p, subValue);
   1.302 +}
   1.303 +
   1.304 +static void MatchFinder_CheckLimits(CMatchFinder *p)
   1.305 +{
   1.306 +  if (p->pos == kMaxValForNormalize)
   1.307 +    MatchFinder_Normalize(p);
   1.308 +  if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
   1.309 +    MatchFinder_CheckAndMoveAndRead(p);
   1.310 +  if (p->cyclicBufferPos == p->cyclicBufferSize)
   1.311 +    p->cyclicBufferPos = 0;
   1.312 +  MatchFinder_SetLimits(p);
   1.313 +}
   1.314 +
   1.315 +static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
   1.316 +    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
   1.317 +    UInt32 *distances, UInt32 maxLen)
   1.318 +{
   1.319 +  son[_cyclicBufferPos] = curMatch;
   1.320 +  for (;;)
   1.321 +  {
   1.322 +    UInt32 delta = pos - curMatch;
   1.323 +    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
   1.324 +      return distances;
   1.325 +    {
   1.326 +      const Byte *pb = cur - delta;
   1.327 +      curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
   1.328 +      if (pb[maxLen] == cur[maxLen] && *pb == *cur)
   1.329 +      {
   1.330 +        UInt32 len = 0;
   1.331 +        while (++len != lenLimit)
   1.332 +          if (pb[len] != cur[len])
   1.333 +            break;
   1.334 +        if (maxLen < len)
   1.335 +        {
   1.336 +          *distances++ = maxLen = len;
   1.337 +          *distances++ = delta - 1;
   1.338 +          if (len == lenLimit)
   1.339 +            return distances;
   1.340 +        }
   1.341 +      }
   1.342 +    }
   1.343 +  }
   1.344 +}
   1.345 +
   1.346 +UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
   1.347 +    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
   1.348 +    UInt32 *distances, UInt32 maxLen)
   1.349 +{
   1.350 +  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
   1.351 +  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
   1.352 +  UInt32 len0 = 0, len1 = 0;
   1.353 +  for (;;)
   1.354 +  {
   1.355 +    UInt32 delta = pos - curMatch;
   1.356 +    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
   1.357 +    {
   1.358 +      *ptr0 = *ptr1 = kEmptyHashValue;
   1.359 +      return distances;
   1.360 +    }
   1.361 +    {
   1.362 +      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
   1.363 +      const Byte *pb = cur - delta;
   1.364 +      UInt32 len = (len0 < len1 ? len0 : len1);
   1.365 +      if (pb[len] == cur[len])
   1.366 +      {
   1.367 +        if (++len != lenLimit && pb[len] == cur[len])
   1.368 +          while (++len != lenLimit)
   1.369 +            if (pb[len] != cur[len])
   1.370 +              break;
   1.371 +        if (maxLen < len)
   1.372 +        {
   1.373 +          *distances++ = maxLen = len;
   1.374 +          *distances++ = delta - 1;
   1.375 +          if (len == lenLimit)
   1.376 +          {
   1.377 +            *ptr1 = pair[0];
   1.378 +            *ptr0 = pair[1];
   1.379 +            return distances;
   1.380 +          }
   1.381 +        }
   1.382 +      }
   1.383 +      if (pb[len] < cur[len])
   1.384 +      {
   1.385 +        *ptr1 = curMatch;
   1.386 +        ptr1 = pair + 1;
   1.387 +        curMatch = *ptr1;
   1.388 +        len1 = len;
   1.389 +      }
   1.390 +      else
   1.391 +      {
   1.392 +        *ptr0 = curMatch;
   1.393 +        ptr0 = pair;
   1.394 +        curMatch = *ptr0;
   1.395 +        len0 = len;
   1.396 +      }
   1.397 +    }
   1.398 +  }
   1.399 +}
   1.400 +
   1.401 +static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
   1.402 +    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
   1.403 +{
   1.404 +  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
   1.405 +  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
   1.406 +  UInt32 len0 = 0, len1 = 0;
   1.407 +  for (;;)
   1.408 +  {
   1.409 +    UInt32 delta = pos - curMatch;
   1.410 +    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
   1.411 +    {
   1.412 +      *ptr0 = *ptr1 = kEmptyHashValue;
   1.413 +      return;
   1.414 +    }
   1.415 +    {
   1.416 +      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
   1.417 +      const Byte *pb = cur - delta;
   1.418 +      UInt32 len = (len0 < len1 ? len0 : len1);
   1.419 +      if (pb[len] == cur[len])
   1.420 +      {
   1.421 +        while (++len != lenLimit)
   1.422 +          if (pb[len] != cur[len])
   1.423 +            break;
   1.424 +        {
   1.425 +          if (len == lenLimit)
   1.426 +          {
   1.427 +            *ptr1 = pair[0];
   1.428 +            *ptr0 = pair[1];
   1.429 +            return;
   1.430 +          }
   1.431 +        }
   1.432 +      }
   1.433 +      if (pb[len] < cur[len])
   1.434 +      {
   1.435 +        *ptr1 = curMatch;
   1.436 +        ptr1 = pair + 1;
   1.437 +        curMatch = *ptr1;
   1.438 +        len1 = len;
   1.439 +      }
   1.440 +      else
   1.441 +      {
   1.442 +        *ptr0 = curMatch;
   1.443 +        ptr0 = pair;
   1.444 +        curMatch = *ptr0;
   1.445 +        len0 = len;
   1.446 +      }
   1.447 +    }
   1.448 +  }
   1.449 +}
   1.450 +
   1.451 +#define MOVE_POS \
   1.452 +  ++p->cyclicBufferPos; \
   1.453 +  p->buffer++; \
   1.454 +  if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
   1.455 +
   1.456 +#define MOVE_POS_RET MOVE_POS return offset;
   1.457 +
   1.458 +static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
   1.459 +
   1.460 +#define GET_MATCHES_HEADER2(minLen, ret_op) \
   1.461 +  UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \
   1.462 +  lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
   1.463 +  cur = p->buffer;
   1.464 +
   1.465 +#define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
   1.466 +#define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)
   1.467 +
   1.468 +#define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
   1.469 +
   1.470 +#define GET_MATCHES_FOOTER(offset, maxLen) \
   1.471 +  offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
   1.472 +  distances + offset, maxLen) - distances); MOVE_POS_RET;
   1.473 +
   1.474 +#define SKIP_FOOTER \
   1.475 +  SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
   1.476 +
   1.477 +static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
   1.478 +{
   1.479 +  UInt32 offset;
   1.480 +  GET_MATCHES_HEADER(2)
   1.481 +  HASH2_CALC;
   1.482 +  curMatch = p->hash[hashValue];
   1.483 +  p->hash[hashValue] = p->pos;
   1.484 +  offset = 0;
   1.485 +  GET_MATCHES_FOOTER(offset, 1)
   1.486 +}
   1.487 +
   1.488 +UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
   1.489 +{
   1.490 +  UInt32 offset;
   1.491 +  GET_MATCHES_HEADER(3)
   1.492 +  HASH_ZIP_CALC;
   1.493 +  curMatch = p->hash[hashValue];
   1.494 +  p->hash[hashValue] = p->pos;
   1.495 +  offset = 0;
   1.496 +  GET_MATCHES_FOOTER(offset, 2)
   1.497 +}
   1.498 +
   1.499 +static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
   1.500 +{
   1.501 +  UInt32 hash2Value, delta2, maxLen, offset;
   1.502 +  GET_MATCHES_HEADER(3)
   1.503 +
   1.504 +  HASH3_CALC;
   1.505 +
   1.506 +  delta2 = p->pos - p->hash[hash2Value];
   1.507 +  curMatch = p->hash[kFix3HashSize + hashValue];
   1.508 +  
   1.509 +  p->hash[hash2Value] =
   1.510 +  p->hash[kFix3HashSize + hashValue] = p->pos;
   1.511 +
   1.512 +
   1.513 +  maxLen = 2;
   1.514 +  offset = 0;
   1.515 +  if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
   1.516 +  {
   1.517 +    for (; maxLen != lenLimit; maxLen++)
   1.518 +      if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
   1.519 +        break;
   1.520 +    distances[0] = maxLen;
   1.521 +    distances[1] = delta2 - 1;
   1.522 +    offset = 2;
   1.523 +    if (maxLen == lenLimit)
   1.524 +    {
   1.525 +      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
   1.526 +      MOVE_POS_RET;
   1.527 +    }
   1.528 +  }
   1.529 +  GET_MATCHES_FOOTER(offset, maxLen)
   1.530 +}
   1.531 +
   1.532 +static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
   1.533 +{
   1.534 +  UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
   1.535 +  GET_MATCHES_HEADER(4)
   1.536 +
   1.537 +  HASH4_CALC;
   1.538 +
   1.539 +  delta2 = p->pos - p->hash[                hash2Value];
   1.540 +  delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
   1.541 +  curMatch = p->hash[kFix4HashSize + hashValue];
   1.542 +  
   1.543 +  p->hash[                hash2Value] =
   1.544 +  p->hash[kFix3HashSize + hash3Value] =
   1.545 +  p->hash[kFix4HashSize + hashValue] = p->pos;
   1.546 +
   1.547 +  maxLen = 1;
   1.548 +  offset = 0;
   1.549 +  if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
   1.550 +  {
   1.551 +    distances[0] = maxLen = 2;
   1.552 +    distances[1] = delta2 - 1;
   1.553 +    offset = 2;
   1.554 +  }
   1.555 +  if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
   1.556 +  {
   1.557 +    maxLen = 3;
   1.558 +    distances[offset + 1] = delta3 - 1;
   1.559 +    offset += 2;
   1.560 +    delta2 = delta3;
   1.561 +  }
   1.562 +  if (offset != 0)
   1.563 +  {
   1.564 +    for (; maxLen != lenLimit; maxLen++)
   1.565 +      if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
   1.566 +        break;
   1.567 +    distances[offset - 2] = maxLen;
   1.568 +    if (maxLen == lenLimit)
   1.569 +    {
   1.570 +      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
   1.571 +      MOVE_POS_RET;
   1.572 +    }
   1.573 +  }
   1.574 +  if (maxLen < 3)
   1.575 +    maxLen = 3;
   1.576 +  GET_MATCHES_FOOTER(offset, maxLen)
   1.577 +}
   1.578 +
   1.579 +static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
   1.580 +{
   1.581 +  UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
   1.582 +  GET_MATCHES_HEADER(4)
   1.583 +
   1.584 +  HASH4_CALC;
   1.585 +
   1.586 +  delta2 = p->pos - p->hash[                hash2Value];
   1.587 +  delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
   1.588 +  curMatch = p->hash[kFix4HashSize + hashValue];
   1.589 +
   1.590 +  p->hash[                hash2Value] =
   1.591 +  p->hash[kFix3HashSize + hash3Value] =
   1.592 +  p->hash[kFix4HashSize + hashValue] = p->pos;
   1.593 +
   1.594 +  maxLen = 1;
   1.595 +  offset = 0;
   1.596 +  if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
   1.597 +  {
   1.598 +    distances[0] = maxLen = 2;
   1.599 +    distances[1] = delta2 - 1;
   1.600 +    offset = 2;
   1.601 +  }
   1.602 +  if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
   1.603 +  {
   1.604 +    maxLen = 3;
   1.605 +    distances[offset + 1] = delta3 - 1;
   1.606 +    offset += 2;
   1.607 +    delta2 = delta3;
   1.608 +  }
   1.609 +  if (offset != 0)
   1.610 +  {
   1.611 +    for (; maxLen != lenLimit; maxLen++)
   1.612 +      if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
   1.613 +        break;
   1.614 +    distances[offset - 2] = maxLen;
   1.615 +    if (maxLen == lenLimit)
   1.616 +    {
   1.617 +      p->son[p->cyclicBufferPos] = curMatch;
   1.618 +      MOVE_POS_RET;
   1.619 +    }
   1.620 +  }
   1.621 +  if (maxLen < 3)
   1.622 +    maxLen = 3;
   1.623 +  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
   1.624 +    distances + offset, maxLen) - (distances));
   1.625 +  MOVE_POS_RET
   1.626 +}
   1.627 +
   1.628 +UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
   1.629 +{
   1.630 +  UInt32 offset;
   1.631 +  GET_MATCHES_HEADER(3)
   1.632 +  HASH_ZIP_CALC;
   1.633 +  curMatch = p->hash[hashValue];
   1.634 +  p->hash[hashValue] = p->pos;
   1.635 +  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
   1.636 +    distances, 2) - (distances));
   1.637 +  MOVE_POS_RET
   1.638 +}
   1.639 +
   1.640 +static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
   1.641 +{
   1.642 +  do
   1.643 +  {
   1.644 +    SKIP_HEADER(2)
   1.645 +    HASH2_CALC;
   1.646 +    curMatch = p->hash[hashValue];
   1.647 +    p->hash[hashValue] = p->pos;
   1.648 +    SKIP_FOOTER
   1.649 +  }
   1.650 +  while (--num != 0);
   1.651 +}
   1.652 +
   1.653 +void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
   1.654 +{
   1.655 +  do
   1.656 +  {
   1.657 +    SKIP_HEADER(3)
   1.658 +    HASH_ZIP_CALC;
   1.659 +    curMatch = p->hash[hashValue];
   1.660 +    p->hash[hashValue] = p->pos;
   1.661 +    SKIP_FOOTER
   1.662 +  }
   1.663 +  while (--num != 0);
   1.664 +}
   1.665 +
   1.666 +static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
   1.667 +{
   1.668 +  do
   1.669 +  {
   1.670 +    UInt32 hash2Value;
   1.671 +    SKIP_HEADER(3)
   1.672 +    HASH3_CALC;
   1.673 +    curMatch = p->hash[kFix3HashSize + hashValue];
   1.674 +    p->hash[hash2Value] =
   1.675 +    p->hash[kFix3HashSize + hashValue] = p->pos;
   1.676 +    SKIP_FOOTER
   1.677 +  }
   1.678 +  while (--num != 0);
   1.679 +}
   1.680 +
   1.681 +static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
   1.682 +{
   1.683 +  do
   1.684 +  {
   1.685 +    UInt32 hash2Value, hash3Value;
   1.686 +    SKIP_HEADER(4)
   1.687 +    HASH4_CALC;
   1.688 +    curMatch = p->hash[kFix4HashSize + hashValue];
   1.689 +    p->hash[                hash2Value] =
   1.690 +    p->hash[kFix3HashSize + hash3Value] = p->pos;
   1.691 +    p->hash[kFix4HashSize + hashValue] = p->pos;
   1.692 +    SKIP_FOOTER
   1.693 +  }
   1.694 +  while (--num != 0);
   1.695 +}
   1.696 +
   1.697 +static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
   1.698 +{
   1.699 +  do
   1.700 +  {
   1.701 +    UInt32 hash2Value, hash3Value;
   1.702 +    SKIP_HEADER(4)
   1.703 +    HASH4_CALC;
   1.704 +    curMatch = p->hash[kFix4HashSize + hashValue];
   1.705 +    p->hash[                hash2Value] =
   1.706 +    p->hash[kFix3HashSize + hash3Value] =
   1.707 +    p->hash[kFix4HashSize + hashValue] = p->pos;
   1.708 +    p->son[p->cyclicBufferPos] = curMatch;
   1.709 +    MOVE_POS
   1.710 +  }
   1.711 +  while (--num != 0);
   1.712 +}
   1.713 +
   1.714 +void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
   1.715 +{
   1.716 +  do
   1.717 +  {
   1.718 +    SKIP_HEADER(3)
   1.719 +    HASH_ZIP_CALC;
   1.720 +    curMatch = p->hash[hashValue];
   1.721 +    p->hash[hashValue] = p->pos;
   1.722 +    p->son[p->cyclicBufferPos] = curMatch;
   1.723 +    MOVE_POS
   1.724 +  }
   1.725 +  while (--num != 0);
   1.726 +}
   1.727 +
   1.728 +void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
   1.729 +{
   1.730 +  vTable->Init = (Mf_Init_Func)MatchFinder_Init;
   1.731 +  vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
   1.732 +  vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
   1.733 +  vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
   1.734 +  if (!p->btMode)
   1.735 +  {
   1.736 +    vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
   1.737 +    vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
   1.738 +  }
   1.739 +  else if (p->numHashBytes == 2)
   1.740 +  {
   1.741 +    vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
   1.742 +    vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
   1.743 +  }
   1.744 +  else if (p->numHashBytes == 3)
   1.745 +  {
   1.746 +    vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
   1.747 +    vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
   1.748 +  }
   1.749 +  else
   1.750 +  {
   1.751 +    vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
   1.752 +    vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
   1.753 +  }
   1.754 +}