patmain.h

pe exe packer (must use vc2005 to compile)

  {
    node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;
    return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
  }
  #endif

  Byte byteXOR;
  UInt32 numSameBits = 0;
  if(numLoadedBits != 0)
  {
    Byte matchByte = *(currentAddingOffset + realMatchPointer -1);  
    matchByte >>= (MY_BYTE_SIZE - numLoadedBits);
    byteXOR = matchByte ^ curByte;
    if(byteXOR != 0)
    {
      AddLeafNode(node, curByte, byteXOR, numSameBits, pos, descendantIndex);
      return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
    }
    numSameBits += numLoadedBits;
  }

  const Byte *matchBytePointer = _buffer + realMatchPointer + 
      (currentBytePointer - baseCurrentBytePointer);
  for(; currentBytePointer < bytePointerLimit; numSameBits += MY_BYTE_SIZE)
  {
    curByte = (*currentBytePointer++);
    *distances++ = pos - realMatchPointer - 1;
    byteXOR = curByte ^ (*matchBytePointer++);
    if(byteXOR != 0)
    {
      AddLeafNode(node, curByte, byteXOR, numSameBits, pos, descendantIndex);
      return kNumHashBytes + (UInt32)(currentBytePointer - baseCurrentBytePointer - 1);
    }
  }
  *distances = pos - realMatchPointer - 1;
  node->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;

  if(*distances == 0)
  {
    m_SpecialMode = true;
    m_NumNotChangedCycles = 0;
  }
  return fullCurrentLimit;
}

STDMETHODIMP_(void) CPatricia::DummyLongestMatch()
{
  GetLongestMatch(m_TmpBacks);
}


// ------------------------------------
// Remove Match

typedef Byte CRemoveDataWord;

static const int kSizeRemoveDataWordInBits = MY_BYTE_SIZE * sizeof(CRemoveDataWord);

#ifndef __AUTO_REMOVE

void CPatricia::RemoveMatch()
{
  if(m_SpecialRemoveMode)
  {
    if(GetIndexByte(_matchMaxLen - 1 - _sizeHistory) ==
        GetIndexByte(_matchMaxLen - _sizeHistory))
      return;
    m_SpecialRemoveMode = false;
  }
  UInt32 pos = _pos + kNumHashBytes - _sizeHistory;

  #ifdef __HASH_3
  const Byte *pp = _buffer + _pos - _sizeHistory;
  UInt32 hash2Value = ((UInt32(pp[0])) << 8) | pp[1];
  UInt32 hashValue = (hash2Value << 8) | pp[2];
  CDescendant &hashDescendant = m_HashDescendants[hashValue];
  CDescendant &hash2Descendant = m_Hash2Descendants[hash2Value];
  if (hash2Descendant >= kMatchStartValue2)
    if(hash2Descendant.MatchPointer == pos + kMatchStartValue2)
      hash2Descendant.MatchPointer = kDescendantEmptyValue2;
  #else
  UInt32 hashValue = UInt32(GetIndexByte(1 - _sizeHistory))  | 
      (UInt32(GetIndexByte(0 - _sizeHistory)) << 8);
  CDescendant &hashDescendant = m_HashDescendants[hashValue];
  #endif
    
  if(hashDescendant.IsEmpty())
    return;
  if(hashDescendant.IsMatch())
  {
    if(hashDescendant.MatchPointer == pos + kMatchStartValue)
      hashDescendant.MakeEmpty();
    return;
  }
  
  UInt32 descendantIndex;
  const CRemoveDataWord *currentPointer = (const CRemoveDataWord *)(_buffer + pos);
  UInt32 numLoadedBits = 0;
  CRemoveDataWord curWord = 0; // = 0 to disable GCC warning

  CIndex *nodePointerPointer = &hashDescendant.NodePointer;

  CNodePointer node = &m_Nodes[hashDescendant.NodePointer];
  
  while(true)
  {
    if(numLoadedBits == 0)
    {
      curWord = *currentPointer++;
      numLoadedBits = kSizeRemoveDataWordInBits; 
    }
    UInt32 numSameBits = node->NumSameBits;
    if(numSameBits > 0)
    {
      if (numLoadedBits <= numSameBits)
      {
        numSameBits -= numLoadedBits;
        currentPointer += (numSameBits / kSizeRemoveDataWordInBits);
        numSameBits %= kSizeRemoveDataWordInBits;
        curWord = *currentPointer++;
        numLoadedBits = kSizeRemoveDataWordInBits; 
      }
      curWord >>= numSameBits;
      numLoadedBits -= numSameBits;
    }
    descendantIndex = (curWord & kSubNodesMask);
    numLoadedBits -= kNumSubBits;
    curWord >>= kNumSubBits;
    UInt32 nextNodeIndex = node->Descendants[descendantIndex].NodePointer;
    if (nextNodeIndex < kDescendantEmptyValue)
    {
      nodePointerPointer = &node->Descendants[descendantIndex].NodePointer;
      node = &m_Nodes[nextNodeIndex];
    }
    else
      break;
  }
  if (node->Descendants[descendantIndex].MatchPointer != pos + kMatchStartValue)
  {
    const Byte *currentBytePointer = _buffer + _pos - _sizeHistory;
    const Byte *currentBytePointerLimit = currentBytePointer + _matchMaxLen;
    for(;currentBytePointer < currentBytePointerLimit; currentBytePointer++)
      if(*currentBytePointer != *(currentBytePointer+1))
        return;
    m_SpecialRemoveMode = true;
    return;
  }

  UInt32 numNodes = 0, numMatches = 0;

  UInt32 i;
  for (i = 0; i < kNumSubNodes; i++)
  {
    UInt32 nodeIndex = node->Descendants[i].NodePointer;
    if (nodeIndex < kDescendantEmptyValue)
      numNodes++;
    else if (nodeIndex > kDescendantEmptyValue)
      numMatches++;
  }
  numMatches -= 1;
  if (numNodes + numMatches > 1)
  {
    node->Descendants[descendantIndex].MakeEmpty();
    return;
  }
  if(numNodes == 1)
  {
    UInt32 i;
    for (i = 0; i < kNumSubNodes; i++)
      if (node->Descendants[i].IsNode())
        break;
    UInt32 nextNodeIndex = node->Descendants[i].NodePointer;
    CNodePointer nextNode = &m_Nodes[nextNodeIndex];
    nextNode->NumSameBits += node->NumSameBits + kNumSubBits;
    *node = *nextNode;

    nextNode->NextFreeNode = m_FreeNode;
    m_FreeNode = nextNodeIndex;
    return;
  }
  UInt32 matchPointer = 0; // = 0 to disable GCC warning
  for (i = 0; i < kNumSubNodes; i++)
    if (node->Descendants[i].IsMatch() && i != descendantIndex)
    {
      matchPointer = node->Descendants[i].MatchPointer;
      break;
    }
  node->NextFreeNode = m_FreeNode;
  m_FreeNode = *nodePointerPointer;
  *nodePointerPointer = matchPointer;
}
#endif


// Commented code is more correct, but it gives warning 
// on GCC: (1 << 32)
// So we use kMatchStartValue twice:
// kMatchStartValue = UInt32(1) << (kNumBitsInIndex - 1);
// must be defined in Pat.h
/*
const UInt32 kNormalizeStartPos = (UInt32(1) << (kNumBitsInIndex)) - 
    kMatchStartValue - kNumHashBytes - 1;
*/
const UInt32 kNormalizeStartPos = kMatchStartValue - kNumHashBytes - 1;

STDMETHODIMP CPatricia::MovePos()
{
  #ifndef __AUTO_REMOVE
  if(_pos >= _sizeHistory)
    RemoveMatch();
  #endif
  RINOK(CLZInWindow::MovePos());
  #ifdef __AUTO_REMOVE
  if (m_NumUsedNodes >= m_NumNodes)
    TestRemoveNodes();
  #endif
  if (_pos >= kNormalizeStartPos)
  {
    #ifdef __AUTO_REMOVE
    TestRemoveNodesAndNormalize();
    #else
    Normalize();
    #endif
  }
  return S_OK;
}

#ifndef __AUTO_REMOVE

void CPatricia::NormalizeDescendant(CDescendant &descendant, UInt32 subValue)
{
  if (descendant.IsEmpty())
    return;
  if (descendant.IsMatch())
    descendant.MatchPointer = descendant.MatchPointer - subValue;
  else
  {
    CNode &node = m_Nodes[descendant.NodePointer];
    node.LastMatch = node.LastMatch - subValue;
    for (UInt32 i = 0; i < kNumSubNodes; i++)
       NormalizeDescendant(node.Descendants[i], subValue);
  }
}

void CPatricia::Normalize()
{
  UInt32 subValue = _pos - _sizeHistory;
  CLZInWindow::ReduceOffsets(subValue);
  
  #ifdef __HASH_3

  for(UInt32 hash = 0; hash < kHash2Size; hash++)
  {
    CDescendant &descendant = m_Hash2Descendants[hash];
    if (descendant.MatchPointer != kDescendantsNotInitilized2)
    {
      UInt32 base = hash << 8;
      for (UInt32 i = 0; i < 0x100; i++)
        NormalizeDescendant(m_HashDescendants[base + i], subValue);
    }
    if (descendant.MatchPointer < kMatchStartValue2)
      continue;
    descendant.MatchPointer = descendant.MatchPointer - subValue;
  }
  
  #else
  
  for(UInt32 hash = 0; hash < kHashSize; hash++)
    NormalizeDescendant(m_HashDescendants[hash], subValue);
  
  #endif

}

#else

void CPatricia::TestRemoveDescendant(CDescendant &descendant, UInt32 limitPos)
{
  CNode &node = m_Nodes[descendant.NodePointer];
  UInt32 numChilds = 0;
  UInt32 childIndex = 0; // = 0 to disable GCC warning
  for (UInt32 i = 0; i < kNumSubNodes; i++)
  {
    CDescendant &descendant2 = node.Descendants[i];
    if (descendant2.IsEmpty())
      continue;
    if (descendant2.IsMatch())
    {
      if (descendant2.MatchPointer < limitPos)
        descendant2.MakeEmpty();
      else
      {
        numChilds++;
        childIndex = i;
      }
    }
    else
    {
      TestRemoveDescendant(descendant2, limitPos);
      if (!descendant2.IsEmpty())
      {
        numChilds++;
        childIndex = i;
      }
    }
  }
  if (numChilds > 1)
    return;

  CIndex nodePointerTemp = descendant.NodePointer;
  if (numChilds == 1)
  {
    const CDescendant &descendant2 = node.Descendants[childIndex];
    if (descendant2.IsNode())
      m_Nodes[descendant2.NodePointer].NumSameBits += node.NumSameBits + kNumSubBits;
    descendant = descendant2;
  }
  else
    descendant.MakeEmpty();
  node.NextFreeNode = m_FreeNode;
  m_FreeNode = nodePointerTemp;
  m_NumUsedNodes--;
}

void CPatricia::RemoveNode(UInt32 index)
{
  CNode &node = m_Nodes[index];
  for (UInt32 i = 0; i < kNumSubNodes; i++)
  {
    CDescendant &descendant2 = node.Descendants[i];
    if (descendant2.IsNode())
      RemoveNode(descendant2.NodePointer);
  }
  node.NextFreeNode = m_FreeNode;
  m_FreeNode = index;
  m_NumUsedNodes--;
}

void CPatricia::TestRemoveNodes()
{
  UInt32 limitPos = kMatchStartValue + _pos - _sizeHistory + kNumHashBytes;
  
  #ifdef __HASH_3
  
  UInt32 limitPos2 = kMatchStartValue2 + _pos - _sizeHistory + kNumHashBytes;
  for(UInt32 hash = 0; hash < kHash2Size; hash++)
  {
    CDescendant &descendant = m_Hash2Descendants[hash];
    if (descendant.MatchPointer != kDescendantsNotInitilized2)
    {
      UInt32 base = hash << 8;
      for (UInt32 i = 0; i < 0x100; i++)
      {
        CDescendant &descendant = m_HashDescendants[base + i];
        if (descendant.IsEmpty())
          continue;
        if (descendant.IsMatch())
        {
          if (descendant.MatchPointer < limitPos)
            descendant.MakeEmpty();
        }
        else
          TestRemoveDescendant(descendant, limitPos);
      }
    }
    if (descendant.MatchPointer < kMatchStartValue2)
      continue;
    if (descendant.MatchPointer < limitPos2)
      descendant.MatchPointer = kDescendantEmptyValue2;
  }
  
  #else
  
  for(UInt32 hash = 0; hash < kHashSize; hash++)
  {
    CDescendant &descendant = m_HashDescendants[hash];
    if (descendant.IsEmpty())
      continue;
    if (descendant.IsMatch())
    {
      if (descendant.MatchPointer < limitPos)
        descendant.MakeEmpty();
    }
    else
      TestRemoveDescendant(descendant, limitPos);
  }
  
  #endif
}

void CPatricia::TestRemoveAndNormalizeDescendant(CDescendant &descendant, 
    UInt32 limitPos, UInt32 subValue)
{
  if (descendant.IsEmpty())
    return;
  if (descendant.IsMatch())
  {
    if (descendant.MatchPointer < limitPos)
      descendant.MakeEmpty();
    else
      descendant.MatchPointer = descendant.MatchPointer - subValue;
    return;
  }
  CNode &node = m_Nodes[descendant.NodePointer];
  UInt32 numChilds = 0;
  UInt32 childIndex = 0; // = 0 to disable GCC warning
  for (UInt32 i = 0; i < kNumSubNodes; i++)
  {
    CDescendant &descendant2 = node.Descendants[i];
    TestRemoveAndNormalizeDescendant(descendant2, limitPos, subValue);
    if (!descendant2.IsEmpty())
    {
      numChilds++;
      childIndex = i;
    }
  }
  if (numChilds > 1)
  {
    node.LastMatch = node.LastMatch - subValue;
    return;
  }

  CIndex nodePointerTemp = descendant.NodePointer;
  if (numChilds == 1)
  {
    const CDescendant &descendant2 = node.Descendants[childIndex];
    if (descendant2.IsNode())
      m_Nodes[descendant2.NodePointer].NumSameBits += node.NumSameBits + kNumSubBits;
    descendant = descendant2;
  }
  else
    descendant.MakeEmpty();
  node.NextFreeNode = m_FreeNode;
  m_FreeNode = nodePointerTemp;
  m_NumUsedNodes--;
}

void CPatricia::TestRemoveNodesAndNormalize()
{
  UInt32 subValue = _pos - _sizeHistory;
  UInt32 limitPos = kMatchStartValue + _pos - _sizeHistory + kNumHashBytes;
  CLZInWindow::ReduceOffsets(subValue);

  #ifdef __HASH_3
  
  UInt32 limitPos2 = kMatchStartValue2 + _pos - _sizeHistory + kNumHashBytes;
  for(UInt32 hash = 0; hash < kHash2Size; hash++)
  {
    CDescendant &descendant = m_Hash2Descendants[hash];
    if (descendant.MatchPointer != kDescendantsNotInitilized2)
    {
      UInt32 base = hash << 8;
      for (UInt32 i = 0; i < 0x100; i++)
        TestRemoveAndNormalizeDescendant(m_HashDescendants[base + i], limitPos, subValue);
    }
    if (descendant.MatchPointer < kMatchStartValue2)
      continue;
    if (descendant.MatchPointer < limitPos2)
      descendant.MatchPointer = kDescendantEmptyValue2;
    else
      descendant.MatchPointer = descendant.MatchPointer - subValue;
  }
  
  #else

  for(UInt32 hash = 0; hash < kHashSize; hash++)
    TestRemoveAndNormalizeDescendant(m_HashDescendants[hash], limitPos, subValue);

  #endif
}

#endif

STDMETHODIMP_(Byte) CPatricia::GetIndexByte(Int32 index)
{
  return CLZInWindow::GetIndexByte(index);
}

STDMETHODIMP_(UInt32) CPatricia::GetMatchLen(Int32 index, UInt32 back, UInt32 limit)
{
  return CLZInWindow::GetMatchLen(index, back, limit);
}

STDMETHODIMP_(UInt32) CPatricia::GetNumAvailableBytes()
{
  return CLZInWindow::GetNumAvailableBytes();
}

STDMETHODIMP_(const Byte *) CPatricia::GetPointerToCurrentPos()
{
  return CLZInWindow::GetPointerToCurrentPos();
}

}