patmain.h

压缩软件源码

// PatMain.h

#include "../../../../Common/Defs.h"
#include "../../../../Common/Alloc.h"

namespace PAT_NAMESPACE {

STDMETHODIMP CPatricia::SetCallback(IMatchFinderCallback *callback)
{
  m_Callback = callback;
  return S_OK;
}

void CPatricia::BeforeMoveBlock()
{
  if (m_Callback)
    m_Callback->BeforeChangingBufferPos();
  CLZInWindow::BeforeMoveBlock();
}

void CPatricia::AfterMoveBlock()
{
  if (m_Callback)
    m_Callback->AfterChangingBufferPos();
  CLZInWindow::AfterMoveBlock();
}

const UInt32 kMatchStartValue2 = 2;
const UInt32 kDescendantEmptyValue2 = kMatchStartValue2 - 1;
const UInt32 kDescendantsNotInitilized2 = kDescendantEmptyValue2 - 1;

#ifdef __HASH_3

static const UInt32 kNumHashBytes = 3;
static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);

static const UInt32 kNumHash2Bytes = 2;
static const UInt32 kHash2Size = 1 << (8 * kNumHash2Bytes);
static const UInt32 kPrevHashSize = kNumHash2Bytes;

#else

static const UInt32 kNumHashBytes = 2;
static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
static const UInt32 kPrevHashSize = 0;

#endif


CPatricia::CPatricia():
  m_HashDescendants(0),
  #ifdef __HASH_3
  m_Hash2Descendants(0),
  #endif
  m_Nodes(0),
  m_TmpBacks(0)
{
}

CPatricia::~CPatricia()
{
  FreeMemory();
}

void CPatricia::FreeMemory()
{
  MyFree(m_TmpBacks);
  m_TmpBacks = 0;

  ::BigFree(m_Nodes);
  m_Nodes = 0;

  ::BigFree(m_HashDescendants);
  m_HashDescendants = 0;

  #ifdef __HASH_3

  ::BigFree(m_Hash2Descendants);
  m_Hash2Descendants = 0;

  CLZInWindow::Free();

  #endif
}
  
STDMETHODIMP CPatricia::Create(UInt32 historySize, UInt32 keepAddBufferBefore, 
    UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
{
  FreeMemory();
  int kNumBitsInNumSameBits = sizeof(CSameBitsType) * 8;
  if (kNumBitsInNumSameBits < 32 && ((matchMaxLen * MY_BYTE_SIZE) > ((UInt32)1 << kNumBitsInNumSameBits)))
    return E_INVALIDARG;

  const UInt32 kAlignMask = (1 << 16) - 1;
  UInt32 windowReservSize = historySize;
  windowReservSize += kAlignMask;
  windowReservSize &= ~(kAlignMask);

  const UInt32 kMinReservSize = (1 << 19);
  if (windowReservSize < kMinReservSize)
    windowReservSize = kMinReservSize;
  windowReservSize += 256;

  if (!CLZInWindow::Create(historySize + keepAddBufferBefore, 
      matchMaxLen + keepAddBufferAfter, windowReservSize))
    return E_OUTOFMEMORY;

  _sizeHistory = historySize;
  _matchMaxLen = matchMaxLen;
  m_HashDescendants = (CDescendant *)BigAlloc(kHashSize * sizeof(CDescendant));
  if (m_HashDescendants == 0)
  {
    FreeMemory();
    return E_OUTOFMEMORY;
  }

  #ifdef __HASH_3
  m_Hash2Descendants = (CDescendant *)BigAlloc(kHash2Size  * sizeof(CDescendant));
  if (m_Hash2Descendants == 0)
  {
    FreeMemory();
    return E_OUTOFMEMORY;
  }
  #endif
  
  #ifdef __AUTO_REMOVE
  
  #ifdef __HASH_3
  m_NumNodes = historySize + _sizeHistory * 4 / 8 + (1 << 19);
  #else
  m_NumNodes = historySize + _sizeHistory * 4 / 8 + (1 << 10);
  #endif
  
  #else
  
  UInt32 m_NumNodes = historySize;
  
  #endif
  
  const UInt32 kMaxNumNodes = UInt32(1) << (sizeof(CIndex) * 8 - 1);
  if (m_NumNodes + 32 > kMaxNumNodes)
    return E_INVALIDARG;
  
  // m_Nodes = (CNode *)::BigAlloc((m_NumNodes + 2) * sizeof(CNode));
  m_Nodes = (CNode *)::BigAlloc((m_NumNodes + 12) * sizeof(CNode));
  if (m_Nodes == 0)
  {
    FreeMemory();
    return E_OUTOFMEMORY;
  }
  
  m_TmpBacks = (UInt32 *)MyAlloc((_matchMaxLen + 1) * sizeof(UInt32));
  if (m_TmpBacks == 0)
  {
    FreeMemory();
    return E_OUTOFMEMORY;
  }
  return S_OK;
}

STDMETHODIMP CPatricia::Init(ISequentialInStream *aStream)
{
  RINOK(CLZInWindow::Init(aStream));

  // memset(m_HashDescendants, 0xFF, kHashSize * sizeof(m_HashDescendants[0]));

  #ifdef __HASH_3
  for (UInt32 i = 0; i < kHash2Size; i++)
    m_Hash2Descendants[i].MatchPointer = kDescendantsNotInitilized2;
  #else
  for (UInt32 i = 0; i < kHashSize; i++)
    m_HashDescendants[i].MakeEmpty();
  #endif

  m_Nodes[0].NextFreeNode = 1;
  m_FreeNode = 0;
  m_FreeNodeMax = 0;
  #ifdef __AUTO_REMOVE
  m_NumUsedNodes = 0;
  #else
  m_SpecialRemoveMode = false;
  #endif
  m_SpecialMode = false;
  return S_OK;
}

STDMETHODIMP_(void) CPatricia::ReleaseStream()
{
  // CLZInWindow::ReleaseStream();
}

// pos = _pos + kNumHashBytes
// fullCurrentLimit = currentLimit + kNumHashBytes
// fullMatchLen = matchLen + kNumHashBytes

void CPatricia::ChangeLastMatch(UInt32 hashValue)
{
  UInt32 pos = _pos + kNumHashBytes - 1;
  UInt32 descendantIndex;
  const Byte *currentBytePointer = _buffer + pos;
  UInt32 numLoadedBits = 0;
  Byte curByte = 0;  // = 0 to disable warning of GCC
  CNodePointer node = &m_Nodes[m_HashDescendants[hashValue].NodePointer];

  while(true)
  {
    UInt32 numSameBits = node->NumSameBits;
    if(numSameBits > 0)
    {
      if (numLoadedBits < numSameBits)
      {
        numSameBits -= numLoadedBits;
        currentBytePointer += (numSameBits / MY_BYTE_SIZE);
        numSameBits %= MY_BYTE_SIZE;
        curByte = *currentBytePointer++;
        numLoadedBits = MY_BYTE_SIZE; 
      }
      curByte >>= numSameBits;
      numLoadedBits -= numSameBits;
    }
    if(numLoadedBits == 0)
    {
      curByte = *currentBytePointer++;
      numLoadedBits = MY_BYTE_SIZE; 
    }
    descendantIndex = (curByte & kSubNodesMask);
    node->LastMatch = pos;
    numLoadedBits -= kNumSubBits;
    curByte >>= kNumSubBits;
    if(node->Descendants[descendantIndex].IsNode())
      node = &m_Nodes[node->Descendants[descendantIndex].NodePointer];
    else
      break;
  }
  node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;
}

UInt32 CPatricia::GetLongestMatch(UInt32 *distances)
{
  UInt32 fullCurrentLimit;
  if (_pos + _matchMaxLen <= _streamPos)
    fullCurrentLimit = _matchMaxLen;
  else
  {
    fullCurrentLimit = _streamPos - _pos;
    if(fullCurrentLimit < kNumHashBytes)
      return 0; 
  }
  UInt32 pos = _pos + kNumHashBytes;

  #ifdef __HASH_3
  UInt32 hash2Value = ((UInt32(_buffer[_pos])) << 8) | _buffer[_pos + 1];
  UInt32 hashValue = (hash2Value << 8) | _buffer[_pos + 2];
  CDescendant &hash2Descendant = m_Hash2Descendants[hash2Value];
  CDescendant &hashDescendant = m_HashDescendants[hashValue];
  if(hash2Descendant.MatchPointer <= kDescendantEmptyValue2)
  {
    if(hash2Descendant.MatchPointer == kDescendantsNotInitilized2)
    {
      UInt32 base = hashValue & 0xFFFF00;
      for (UInt32 i = 0; i < 0x100; i++)
        m_HashDescendants[base + i].MakeEmpty();
    }
    hash2Descendant.MatchPointer = pos + kMatchStartValue2;
    hashDescendant.MatchPointer = pos + kMatchStartValue;
    return 0;
  }

  distances[kNumHash2Bytes] = pos - (hash2Descendant.MatchPointer - kMatchStartValue2) - 1;
  hash2Descendant.MatchPointer = pos + kMatchStartValue2;
  #ifdef __AUTO_REMOVE
  if (distances[kNumHash2Bytes] >= _sizeHistory)
  {
    if (hashDescendant.IsNode())
      RemoveNode(hashDescendant.NodePointer);
    hashDescendant.MatchPointer = pos + kMatchStartValue;
    return 0;
  }
  #endif
  if (fullCurrentLimit == kNumHash2Bytes)
    return kNumHash2Bytes;

  #else
  UInt32 hashValue = UInt32(GetIndexByte(1))  | (UInt32(GetIndexByte(0)) << 8);
  CDescendant &hashDescendant = m_HashDescendants[hashValue];
  #endif


  if(m_SpecialMode)
  {
    if(hashDescendant.IsMatch())
      m_NumNotChangedCycles = 0;
    if(m_NumNotChangedCycles >= _sizeHistory - 1)
    {
      ChangeLastMatch(hashValue);
      m_NumNotChangedCycles = 0;
    }
    if(GetIndexByte(fullCurrentLimit - 1) == GetIndexByte(fullCurrentLimit - 2)) 
    {
      if(hashDescendant.IsMatch())
        hashDescendant.MatchPointer = pos + kMatchStartValue;
      else
        m_NumNotChangedCycles++;
      for(UInt32 i = kNumHashBytes; i <= fullCurrentLimit; i++)
        distances[i] = 0;
      return fullCurrentLimit;
    }
    else if(m_NumNotChangedCycles > 0)
      ChangeLastMatch(hashValue);
    m_SpecialMode = false;
  }

  if(hashDescendant.IsEmpty())
  {
    hashDescendant.MatchPointer = pos + kMatchStartValue;
    return kPrevHashSize;
  }

  UInt32 currentLimit = fullCurrentLimit - kNumHashBytes;

  if(hashDescendant.IsMatch())
  {
    CMatchPointer matchPointer = hashDescendant.MatchPointer;
    UInt32 backReal = pos - (matchPointer - kMatchStartValue);
    UInt32 back = backReal - 1;
    #ifdef __AUTO_REMOVE
    if (back >= _sizeHistory)
    {
      hashDescendant.MatchPointer = pos + kMatchStartValue;
      return kPrevHashSize;
    }
    #endif

    UInt32 matchLen;
    distances += kNumHashBytes;
    Byte *buffer = _buffer + pos;
    for(matchLen = 0; true; matchLen++)
    {
      *distances++ = back;
      if (matchLen == currentLimit)
      {
        hashDescendant.MatchPointer = pos + kMatchStartValue;
        return kNumHashBytes + matchLen;
      }
      if (buffer[matchLen] != buffer[(size_t)matchLen - backReal])
        break;
    }
     
    // UInt32 matchLen = GetMatchLen(kNumHashBytes, back, currentLimit);
    
    UInt32 fullMatchLen = matchLen + kNumHashBytes; 
    hashDescendant.NodePointer = m_FreeNode;
    CNodePointer node = &m_Nodes[m_FreeNode];
    m_FreeNode = node->NextFreeNode;
    #ifdef __AUTO_REMOVE
    m_NumUsedNodes++;
    #endif
    if (m_FreeNode > m_FreeNodeMax)
    {
      m_FreeNodeMax = m_FreeNode;
      m_Nodes[m_FreeNode].NextFreeNode = m_FreeNode + 1;
    }
      
    for (UInt32 i = 0; i < kNumSubNodes; i++)
      node->Descendants[i].NodePointer = kDescendantEmptyValue;
    node->LastMatch = pos;
      
    Byte byteNew = GetIndexByte(fullMatchLen);
    Byte byteOld = GetIndexByte(fullMatchLen - backReal);
    Byte bitsNew, bitsOld;
    UInt32 numSameBits = matchLen * MY_BYTE_SIZE;
    while (true)
    {
      bitsNew = (byteNew & kSubNodesMask);
      bitsOld = (byteOld & kSubNodesMask);
      if(bitsNew != bitsOld) 
        break;
      byteNew >>= kNumSubBits;
      byteOld >>= kNumSubBits;
      numSameBits += kNumSubBits;
    }
    node->NumSameBits = CSameBitsType(numSameBits);
    node->Descendants[bitsNew].MatchPointer = pos + kMatchStartValue;
    node->Descendants[bitsOld].MatchPointer = matchPointer;
    return fullMatchLen;
  }
  const Byte *baseCurrentBytePointer = _buffer + pos;
  const Byte *currentBytePointer = baseCurrentBytePointer;
  UInt32 numLoadedBits = 0;
  Byte curByte = 0;
  CIndex *nodePointerPointer = &hashDescendant.NodePointer;
  CNodePointer node = &m_Nodes[*nodePointerPointer];
  distances += kNumHashBytes;
  const Byte *bytePointerLimit = baseCurrentBytePointer + currentLimit;
  const Byte *currentAddingOffset = _buffer;

  #ifdef __AUTO_REMOVE
  UInt32 lowPos;
  if (pos > _sizeHistory)
    lowPos = pos - _sizeHistory;
  else
    lowPos = 0;
  #endif

  while(true)
  {
    #ifdef __AUTO_REMOVE
    if (node->LastMatch < lowPos)
    {
      RemoveNode(*nodePointerPointer);
      *nodePointerPointer = pos + kMatchStartValue;
      if (currentBytePointer == baseCurrentBytePointer)
        return kPrevHashSize;
      return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
    }
    #endif
    if(numLoadedBits == 0)
    {
      *distances++ = pos - node->LastMatch - 1;
      if(currentBytePointer >= bytePointerLimit)
      {
        for (UInt32 i = 0; i < kNumSubNodes; i++)
          node->Descendants[i].MatchPointer = pos + kMatchStartValue;
        node->LastMatch = pos;
        node->NumSameBits = 0;
        return fullCurrentLimit;
      }
      curByte = (*currentBytePointer++);
      currentAddingOffset++;
      numLoadedBits = MY_BYTE_SIZE; 
    }
    UInt32 numSameBits = node->NumSameBits;
    if(numSameBits > 0)
    {
      Byte byteXOR = ((*(currentAddingOffset + node->LastMatch -1)) >> 
          (MY_BYTE_SIZE - numLoadedBits)) ^ curByte;
      while(numLoadedBits <= numSameBits)
      {
        if(byteXOR != 0)
        {
          AddInternalNode(node, nodePointerPointer, curByte, byteXOR,
              numSameBits, pos);
          return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
        }
        *distances++ = pos - node->LastMatch - 1;
        numSameBits -= numLoadedBits;
        if(currentBytePointer >= bytePointerLimit)
        {
          for (UInt32 i = 0; i < kNumSubNodes; i++)
            node->Descendants[i].MatchPointer = pos + kMatchStartValue;
          node->LastMatch = pos;
          node->NumSameBits = CSameBitsType(node->NumSameBits - numSameBits);
          return fullCurrentLimit;
        }
        numLoadedBits = MY_BYTE_SIZE; 
        curByte = (*currentBytePointer++);
        byteXOR = curByte ^ (*(currentAddingOffset + node->LastMatch));
        currentAddingOffset++;
      }
      if((byteXOR & ((1 << numSameBits) - 1)) != 0)
      {
        AddInternalNode(node, nodePointerPointer, curByte, byteXOR,
            numSameBits, pos);
        return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
      }
      curByte >>= numSameBits;
      numLoadedBits -= numSameBits;
    }
    UInt32 descendantIndex = (curByte & kSubNodesMask);
    numLoadedBits -= kNumSubBits;
    nodePointerPointer = &node->Descendants[descendantIndex].NodePointer;
    UInt32 nextNodeIndex = *nodePointerPointer;
    node->LastMatch = pos;
    if (nextNodeIndex < kDescendantEmptyValue)
    {
      curByte >>= kNumSubBits;
      node = &m_Nodes[nextNodeIndex];
    }
    else if (nextNodeIndex == kDescendantEmptyValue)
    {
      node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;
      return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
    }
    else 
      break;
  }
 
  UInt32 descendantIndex = (curByte & kSubNodesMask);
  curByte >>= kNumSubBits;
  CMatchPointer matchPointer = node->Descendants[descendantIndex].MatchPointer;
  CMatchPointer realMatchPointer;
  realMatchPointer = matchPointer - kMatchStartValue;

  #ifdef __AUTO_REMOVE
  if (realMatchPointer < lowPos)