OptIO/src/LzFind.c

/* LzFind.c -- Match finder for LZ algorithms
2008-10-04 : Igor Pavlov : Public domain */

#include <string.h>

#include "LzFind.h"
#include "LzHash.h"

#define kEmptyHashValue 0
#define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
#define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
#define kNormalizeMask (~(kNormalizeStepMin - 1))
#define kMaxHistorySize ((UInt32)3 << 30)

#define kStartMaxLen 3

static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
{
  if (!p->directInput)
  {
    alloc->Free(alloc, p->bufferBase);
    p->bufferBase = 0;
  }
}

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

static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)
{
  UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
  if (p->directInput)
  {
    p->blockSize = blockSize;
    return 1;
  }
  if (p->bufferBase == 0 || p->blockSize != blockSize)
  {
    LzInWindow_Free(p, alloc);
    p->blockSize = blockSize;
    p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
  }
  return (p->bufferBase != 0);
}

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

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

void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
{
  p->posLimit -= subValue;
  p->pos -= subValue;
  p->streamPos -= subValue;
}

static void MatchFinder_ReadBlock(CMatchFinder *p)
{
  if (p->streamEndWasReached || p->result != SZ_OK)
    return;
  for (;;)
  {
    Byte *dest = p->buffer + (p->streamPos - p->pos);
    size_t size = (p->bufferBase + p->blockSize - dest);
    if (size == 0)
      return;
    p->result = p->stream->Read(p->stream, dest, &size);
    if (p->result != SZ_OK)
      return;
    if (size == 0)
    {
      p->streamEndWasReached = 1;
      return;
    }
    p->streamPos += (UInt32)size;
    if (p->streamPos - p->pos > p->keepSizeAfter)
      return;
  }
}

void MatchFinder_MoveBlock(CMatchFinder *p)
{
  memmove(p->bufferBase,
    p->buffer - p->keepSizeBefore,
    (size_t)(p->streamPos - p->pos + p->keepSizeBefore));
  p->buffer = p->bufferBase + p->keepSizeBefore;
}

int MatchFinder_NeedMove(CMatchFinder *p)
{
  /* if (p->streamEndWasReached) return 0; */
  return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
}

void MatchFinder_ReadIfRequired(CMatchFinder *p)
{
  if (p->streamEndWasReached)
    return;
  if (p->keepSizeAfter >= p->streamPos - p->pos)
    MatchFinder_ReadBlock(p);
}

static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
{
  if (MatchFinder_NeedMove(p))
    MatchFinder_MoveBlock(p);
  MatchFinder_ReadBlock(p);
}

static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
{
  p->cutValue = 32;
  p->btMode = 1;
  p->numHashBytes = 4;
  /* p->skipModeBits = 0; */
  p->directInput = 0;
  p->bigHash = 0;
}

#define kCrcPoly 0xEDB88320

void MatchFinder_Construct(CMatchFinder *p)
{
  UInt32 i;
  p->bufferBase = 0;
  p->directInput = 0;
  p->hash = 0;
  MatchFinder_SetDefaultSettings(p);

  for (i = 0; i < 256; i++)
  {
    UInt32 r = i;
    int j;
    for (j = 0; j < 8; j++)
      r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
    p->crc[i] = r;
  }
}

static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
{
  alloc->Free(alloc, p->hash);
  p->hash = 0;
}

void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
{
  MatchFinder_FreeThisClassMemory(p, alloc);
  LzInWindow_Free(p, alloc);
}

static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)
{
  size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
  if (sizeInBytes / sizeof(CLzRef) != num)
    return 0;
  return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
}

int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
    UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
    ISzAlloc *alloc)
{
  UInt32 sizeReserv;
  if (historySize > kMaxHistorySize)
  {
    MatchFinder_Free(p, alloc);
    return 0;
  }
  sizeReserv = historySize >> 1;
  if (historySize > ((UInt32)2 << 30))
    sizeReserv = historySize >> 2;
  sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);

  p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
  p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
  /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
  if (LzInWindow_Create(p, sizeReserv, alloc))
  {
    UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;
    UInt32 hs;
    p->matchMaxLen = matchMaxLen;
    {
      p->fixedHashSize = 0;
      if (p->numHashBytes == 2)
        hs = (1 << 16) - 1;
      else
      {
        hs = historySize - 1;
        hs |= (hs >> 1);
        hs |= (hs >> 2);
        hs |= (hs >> 4);
        hs |= (hs >> 8);
        hs >>= 1;
        /* hs >>= p->skipModeBits; */
        hs |= 0xFFFF; /* don't change it! It's required for Deflate */
        if (hs > (1 << 24))
        {
          if (p->numHashBytes == 3)
            hs = (1 << 24) - 1;
          else
            hs >>= 1;
        }
      }
      p->hashMask = hs;
      hs++;
      if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
      if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
      if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
      hs += p->fixedHashSize;
    }

    {
      UInt32 prevSize = p->hashSizeSum + p->numSons;
      UInt32 newSize;
      p->historySize = historySize;
      p->hashSizeSum = hs;
      p->cyclicBufferSize = newCyclicBufferSize;
      p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
      newSize = p->hashSizeSum + p->numSons;
      if (p->hash != 0 && prevSize == newSize)
        return 1;
      MatchFinder_FreeThisClassMemory(p, alloc);
      p->hash = AllocRefs(newSize, alloc);
      if (p->hash != 0)
      {
        p->son = p->hash + p->hashSizeSum;
        return 1;
      }
    }
  }
  MatchFinder_Free(p, alloc);
  return 0;
}

static void MatchFinder_SetLimits(CMatchFinder *p)
{
  UInt32 limit = kMaxValForNormalize - p->pos;
  UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
  if (limit2 < limit)
    limit = limit2;
  limit2 = p->streamPos - p->pos;
  if (limit2 <= p->keepSizeAfter)
  {
    if (limit2 > 0)
      limit2 = 1;
  }
  else
    limit2 -= p->keepSizeAfter;
  if (limit2 < limit)
    limit = limit2;
  {
    UInt32 lenLimit = p->streamPos - p->pos;
    if (lenLimit > p->matchMaxLen)
      lenLimit = p->matchMaxLen;
    p->lenLimit = lenLimit;
  }
  p->posLimit = p->pos + limit;
}

void MatchFinder_Init(CMatchFinder *p)
{
  UInt32 i;
  for (i = 0; i < p->hashSizeSum; i++)
    p->hash[i] = kEmptyHashValue;
  p->cyclicBufferPos = 0;
  p->buffer = p->bufferBase;
  p->pos = p->streamPos = p->cyclicBufferSize;
  p->result = SZ_OK;
  p->streamEndWasReached = 0;
  MatchFinder_ReadBlock(p);
  MatchFinder_SetLimits(p);
}

static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
{
  return (p->pos - p->historySize - 1) & kNormalizeMask;
}

void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
{
  UInt32 i;
  for (i = 0; i < numItems; i++)
  {
    UInt32 value = items[i];
    if (value <= subValue)
      value = kEmptyHashValue;
    else
      value -= subValue;
    items[i] = value;
  }
}

static void MatchFinder_Normalize(CMatchFinder *p)
{
  UInt32 subValue = MatchFinder_GetSubValue(p);
  MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
  MatchFinder_ReduceOffsets(p, subValue);
}

static void MatchFinder_CheckLimits(CMatchFinder *p)
{
  if (p->pos == kMaxValForNormalize)
    MatchFinder_Normalize(p);
  if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
    MatchFinder_CheckAndMoveAndRead(p);
  if (p->cyclicBufferPos == p->cyclicBufferSize)
    p->cyclicBufferPos = 0;
  MatchFinder_SetLimits(p);
}

static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
    UInt32 *distances, UInt32 maxLen)
{
  son[_cyclicBufferPos] = curMatch;
  for (;;)
  {
    UInt32 delta = pos - curMatch;
    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
      return distances;
    {
      const Byte *pb = cur - delta;
      curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
      if (pb[maxLen] == cur[maxLen] && *pb == *cur)
      {
        UInt32 len = 0;
        while (++len != lenLimit)
          if (pb[len] != cur[len])
            break;
        if (maxLen < len)
        {
          *distances++ = maxLen = len;
          *distances++ = delta - 1;
          if (len == lenLimit)
            return distances;
        }
      }
    }
  }
}

UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
    UInt32 *distances, UInt32 maxLen)
{
  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
  UInt32 len0 = 0, len1 = 0;
  for (;;)
  {
    UInt32 delta = pos - curMatch;
    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
    {
      *ptr0 = *ptr1 = kEmptyHashValue;
      return distances;
    }
    {
      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
      const Byte *pb = cur - delta;
      UInt32 len = (len0 < len1 ? len0 : len1);
      if (pb[len] == cur[len])
      {
        if (++len != lenLimit && pb[len] == cur[len])
          while (++len != lenLimit)
            if (pb[len] != cur[len])
              break;
        if (maxLen < len)
        {
          *distances++ = maxLen = len;
          *distances++ = delta - 1;
          if (len == lenLimit)
          {
            *ptr1 = pair[0];
            *ptr0 = pair[1];
            return distances;
          }
        }
      }
      if (pb[len] < cur[len])
      {
        *ptr1 = curMatch;
        ptr1 = pair + 1;
        curMatch = *ptr1;
        len1 = len;
      }
      else
      {
        *ptr0 = curMatch;
        ptr0 = pair;
        curMatch = *ptr0;
        len0 = len;
      }
    }
  }
}

static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
{
  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
  UInt32 len0 = 0, len1 = 0;
  for (;;)
  {
    UInt32 delta = pos - curMatch;
    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
    {
      *ptr0 = *ptr1 = kEmptyHashValue;
      return;
    }
    {
      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
      const Byte *pb = cur - delta;
      UInt32 len = (len0 < len1 ? len0 : len1);
      if (pb[len] == cur[len])
      {
        while (++len != lenLimit)
          if (pb[len] != cur[len])
            break;
        {
          if (len == lenLimit)
          {
            *ptr1 = pair[0];
            *ptr0 = pair[1];
            return;
          }
        }
      }
      if (pb[len] < cur[len])
      {
        *ptr1 = curMatch;
        ptr1 = pair + 1;
        curMatch = *ptr1;
        len1 = len;
      }
      else
      {
        *ptr0 = curMatch;
        ptr0 = pair;
        curMatch = *ptr0;
        len0 = len;
      }
    }
  }
}

#define MOVE_POS \
  ++p->cyclicBufferPos; \
  p->buffer++; \
  if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);

#define MOVE_POS_RET MOVE_POS return offset;

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

#define GET_MATCHES_HEADER2(minLen, ret_op) \
  UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \
  lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
  cur = p->buffer;

#define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
#define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)

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

#define GET_MATCHES_FOOTER(offset, maxLen) \
  offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
  distances + offset, maxLen) - distances); MOVE_POS_RET;

#define SKIP_FOOTER \
  SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;

static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
{
  UInt32 offset;
  GET_MATCHES_HEADER(2)
  HASH2_CALC;
  curMatch = p->hash[hashValue];
  p->hash[hashValue] = p->pos;
  offset = 0;
  GET_MATCHES_FOOTER(offset, 1)
}

UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
{
  UInt32 offset;
  GET_MATCHES_HEADER(3)
  HASH_ZIP_CALC;
  curMatch = p->hash[hashValue];
  p->hash[hashValue] = p->pos;
  offset = 0;
  GET_MATCHES_FOOTER(offset, 2)
}

static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
{
  UInt32 hash2Value, delta2, maxLen, offset;
  GET_MATCHES_HEADER(3)

  HASH3_CALC;

  delta2 = p->pos - p->hash[hash2Value];
  curMatch = p->hash[kFix3HashSize + hashValue];
  
  p->hash[hash2Value] =
  p->hash[kFix3HashSize + hashValue] = p->pos;


  maxLen = 2;
  offset = 0;
  if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
  {
    for (; maxLen != lenLimit; maxLen++)
      if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
        break;
    distances[0] = maxLen;
    distances[1] = delta2 - 1;
    offset = 2;
    if (maxLen == lenLimit)
    {
      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
      MOVE_POS_RET;
    }
  }
  GET_MATCHES_FOOTER(offset, maxLen)
}

static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
{
  UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
  GET_MATCHES_HEADER(4)

  HASH4_CALC;

  delta2 = p->pos - p->hash[                hash2Value];
  delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
  curMatch = p->hash[kFix4HashSize + hashValue];
  
  p->hash[                hash2Value] =
  p->hash[kFix3HashSize + hash3Value] =
  p->hash[kFix4HashSize + hashValue] = p->pos;

  maxLen = 1;
  offset = 0;
  if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
  {
    distances[0] = maxLen = 2;
    distances[1] = delta2 - 1;
    offset = 2;
  }
  if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
  {
    maxLen = 3;
    distances[offset + 1] = delta3 - 1;
    offset += 2;
    delta2 = delta3;
  }
  if (offset != 0)
  {
    for (; maxLen != lenLimit; maxLen++)
      if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
        break;
    distances[offset - 2] = maxLen;
    if (maxLen == lenLimit)
    {
      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
      MOVE_POS_RET;
    }
  }
  if (maxLen < 3)
    maxLen = 3;
  GET_MATCHES_FOOTER(offset, maxLen)
}

static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
{
  UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
  GET_MATCHES_HEADER(4)

  HASH4_CALC;

  delta2 = p->pos - p->hash[                hash2Value];
  delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
  curMatch = p->hash[kFix4HashSize + hashValue];

  p->hash[                hash2Value] =
  p->hash[kFix3HashSize + hash3Value] =
  p->hash[kFix4HashSize + hashValue] = p->pos;

  maxLen = 1;
  offset = 0;
  if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
  {
    distances[0] = maxLen = 2;
    distances[1] = delta2 - 1;
    offset = 2;
  }
  if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
  {
    maxLen = 3;
    distances[offset + 1] = delta3 - 1;
    offset += 2;
    delta2 = delta3;
  }
  if (offset != 0)
  {
    for (; maxLen != lenLimit; maxLen++)
      if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
        break;
    distances[offset - 2] = maxLen;
    if (maxLen == lenLimit)
    {
      p->son[p->cyclicBufferPos] = curMatch;
      MOVE_POS_RET;
    }
  }
  if (maxLen < 3)
    maxLen = 3;
  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
    distances + offset, maxLen) - (distances));
  MOVE_POS_RET
}

UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
{
  UInt32 offset;
  GET_MATCHES_HEADER(3)
  HASH_ZIP_CALC;
  curMatch = p->hash[hashValue];
  p->hash[hashValue] = p->pos;
  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
    distances, 2) - (distances));
  MOVE_POS_RET
}

static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
{
  do
  {
    SKIP_HEADER(2)
    HASH2_CALC;
    curMatch = p->hash[hashValue];
    p->hash[hashValue] = p->pos;
    SKIP_FOOTER
  }
  while (--num != 0);
}

void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
{
  do
  {
    SKIP_HEADER(3)
    HASH_ZIP_CALC;
    curMatch = p->hash[hashValue];
    p->hash[hashValue] = p->pos;
    SKIP_FOOTER
  }
  while (--num != 0);
}

static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
{
  do
  {
    UInt32 hash2Value;
    SKIP_HEADER(3)
    HASH3_CALC;
    curMatch = p->hash[kFix3HashSize + hashValue];
    p->hash[hash2Value] =
    p->hash[kFix3HashSize + hashValue] = p->pos;
    SKIP_FOOTER
  }
  while (--num != 0);
}

static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
{
  do
  {
    UInt32 hash2Value, hash3Value;
    SKIP_HEADER(4)
    HASH4_CALC;
    curMatch = p->hash[kFix4HashSize + hashValue];
    p->hash[                hash2Value] =
    p->hash[kFix3HashSize + hash3Value] = p->pos;
    p->hash[kFix4HashSize + hashValue] = p->pos;
    SKIP_FOOTER
  }
  while (--num != 0);
}

static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
{
  do
  {
    UInt32 hash2Value, hash3Value;
    SKIP_HEADER(4)
    HASH4_CALC;
    curMatch = p->hash[kFix4HashSize + hashValue];
    p->hash[                hash2Value] =
    p->hash[kFix3HashSize + hash3Value] =
    p->hash[kFix4HashSize + hashValue] = p->pos;
    p->son[p->cyclicBufferPos] = curMatch;
    MOVE_POS
  }
  while (--num != 0);
}

void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
{
  do
  {
    SKIP_HEADER(3)
    HASH_ZIP_CALC;
    curMatch = p->hash[hashValue];
    p->hash[hashValue] = p->pos;
    p->son[p->cyclicBufferPos] = curMatch;
    MOVE_POS
  }
  while (--num != 0);
}

void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
{
  vTable->Init = (Mf_Init_Func)MatchFinder_Init;
  vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
  vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
  vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
  if (!p->btMode)
  {
    vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
    vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
  }
  else if (p->numHashBytes == 2)
  {
    vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
    vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
  }
  else if (p->numHashBytes == 3)
  {
    vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
    vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
  }
  else
  {
    vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
    vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
  }
}
Revision:	1.1
Committed:	Tue Feb 24 20:13:57 2009 UTC (16 years, 2 months ago) by loizides
Content type:	text/plain
Branch:	MAIN
CVS Tags:	Mit_032, Mit_031, Mit_025c_branch2, Mit_025c_branch1, Mit_030, Mit_029c, Mit_030_pre1, Mit_029a, Mit_029, Mit_029_pre1, Mit_028a, Mit_025c_branch0, Mit_028, Mit_027a, Mit_027, Mit_026, Mit_025e, Mit_025d, Mit_025c, Mit_025b, Mit_025a, Mit_025, Mit_025pre2, Mit_024b, Mit_025pre1, Mit_024a, Mit_024, Mit_023, Mit_022a, Mit_022, Mit_020d, TMit_020d, Mit_020c, Mit_021, Mit_021pre2, Mit_021pre1, Mit_020b, Mit_020a, Mit_020, Mit_020pre1, Mit_018, Mit_017, Mit_017pre3, Mit_017pre2, Mit_017pre1, V07-05-00, Mit_016, Mit_015b, Mit_015a, Mit_015, Mit_014e, Mit_014d, Mit_014c, Mit_014b, ConvRejection-10-06-09, Mit_014a, Mit_014, Mit_014pre3, Mit_014pre2, Mit_014pre1, Mit_013d, Mit_013c, Mit_013b, Mit_013a, Mit_013, Mit_013pre1, Mit_012i, Mit_012g, Mit_012f, Mit_012e, Mit_012d, Mit_012c, Mit_012b, Mit_012a, Mit_012, Mit_011a, Mit_011, Mit_010a, Mit_010, Mit_009c, Mit_009b, Mit_009a, Mit_009, Mit_008, Mit_008pre2, Mit_008pre1, HEAD
Branch point for:	Mit_025c_branch
Log Message:	Added lzma
#	Content
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	}