patmain.h

7-Zip 3.11的源码

  {
    aNode->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;
    return kNumHashBytes + (aCurrentBytePointer - aBaseCurrentBytePointer - 1);
  }
  #endif

  BYTE aByteXOR;
  UINT32 aNumSameBits = 0;
  if(aNumLoadedBits != 0)
  {
    BYTE aMatchByte = *(aCurrentAddingOffset + aRealMatchPointer -1);  
    aMatchByte >>= (MY_BYTE_SIZE - aNumLoadedBits);
    aByteXOR = aMatchByte ^ aByte;
    if(aByteXOR != 0)
    {
      AddLeafNode(aNode, aByte, aByteXOR, aNumSameBits, pos, descendantIndex);
      return kNumHashBytes + (aCurrentBytePointer - aBaseCurrentBytePointer - 1);
    }
    aNumSameBits += aNumLoadedBits;
  }

  const BYTE *aMatchBytePointer = _buffer + aRealMatchPointer + 
      (aCurrentBytePointer - aBaseCurrentBytePointer);
  for(; aCurrentBytePointer < aBytePointerLimit; aNumSameBits += MY_BYTE_SIZE)
  {
    aByte = (*aCurrentBytePointer++);
    *aBacks++ = pos - aRealMatchPointer - 1;
    aByteXOR = aByte ^ (*aMatchBytePointer++);
    if(aByteXOR != 0)
    {
      AddLeafNode(aNode, aByte, aByteXOR, aNumSameBits, pos, descendantIndex);
      return kNumHashBytes + (aCurrentBytePointer - aBaseCurrentBytePointer - 1);
    }
  }
  *aBacks = pos - aRealMatchPointer - 1;
  aNode->Descendants[descendantIndex].MatchPointer = pos + kMatchStartValue;

  if(*aBacks == 0)
  {
    m_SpecialMode = true;
    m_NumNotChangedCycles = 0;
  }
  return aFullCurrentLimit;
}

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
  // UINT32 aHashValue = (*((UINT32 *)(_buffer + _pos - _sizeHistory))) & 0xFFFFFF;
  UINT32 aHashValueTemp = *((UINT32 *)(_buffer + _pos - _sizeHistory));
  UINT32 aHashValue = ((aHashValueTemp << 8) | 
      ((aHashValueTemp & 0xFFFFFF)>> 16)) & 0xFFFFFF;

  CDescendant &aHashDescendant = m_HashDescendants[aHashValue];
  CDescendant &aHash2Descendant = m_Hash2Descendants[aHashValueTemp & 0xFFFF];
  if (aHash2Descendant >= kMatchStartValue2)
    if(aHash2Descendant.MatchPointer == pos + kMatchStartValue2)
      aHash2Descendant.MatchPointer = kDescendantEmptyValue2;
  #else
  UINT32 aHashValue = UINT32(GetIndexByte(1 - _sizeHistory))  | 
      (UINT32(GetIndexByte(0 - _sizeHistory)) << 8);
  CDescendant &aHashDescendant = m_HashDescendants[aHashValue];
  #endif
    
  if(aHashDescendant.IsEmpty())
    return;
  if(aHashDescendant.IsMatch())
  {
    if(aHashDescendant.MatchPointer == pos + kMatchStartValue)
      aHashDescendant.MakeEmpty();
    return;
  }
  
  UINT32 descendantIndex;
  const CRemoveDataWord *aCurrentPointer = (const CRemoveDataWord *)(_buffer + pos);
  UINT32 aNumLoadedBits = 0;
  CRemoveDataWord aWord;

  CIndex *aNodePointerPointer = &aHashDescendant.NodePointer;

  CNodePointer aNode = &m_Nodes[aHashDescendant.NodePointer];
  
  while(true)
  {
    if(aNumLoadedBits == 0)
    {
      aWord = *aCurrentPointer++;
      aNumLoadedBits = kSizeRemoveDataWordInBits; 
    }
    UINT32 aNumSameBits = aNode->NumSameBits;
    if(aNumSameBits > 0)
    {
      if (aNumLoadedBits <= aNumSameBits)
      {
        aNumSameBits -= aNumLoadedBits;
        aCurrentPointer += (aNumSameBits / kSizeRemoveDataWordInBits);
        aNumSameBits %= kSizeRemoveDataWordInBits;
        aWord = *aCurrentPointer++;
        aNumLoadedBits = kSizeRemoveDataWordInBits; 
      }
      aWord >>= aNumSameBits;
      aNumLoadedBits -= aNumSameBits;
    }
    descendantIndex = (aWord & kSubNodesMask);
    aNumLoadedBits -= kNumSubBits;
    aWord >>= kNumSubBits;
    UINT32 aNextNodeIndex = aNode->Descendants[descendantIndex].NodePointer;
    if (aNextNodeIndex < kDescendantEmptyValue)
    {
      aNodePointerPointer = &aNode->Descendants[descendantIndex].NodePointer;
      aNode = &m_Nodes[aNextNodeIndex];
    }
    else
      break;
  }
  if (aNode->Descendants[descendantIndex].MatchPointer != pos + kMatchStartValue)
  {
    const BYTE *aCurrentBytePointer = _buffer + _pos - _sizeHistory;
    const BYTE *aCurrentBytePointerLimit = aCurrentBytePointer + _matchMaxLen;
    for(;aCurrentBytePointer < aCurrentBytePointerLimit; aCurrentBytePointer++)
      if(*aCurrentBytePointer != *(aCurrentBytePointer+1))
        return;
    m_SpecialRemoveMode = true;
    return;
  }

  UINT32 aNumNodes = 0, aNumMatches = 0;

  UINT32 i;
  for (i = 0; i < kNumSubNodes; i++)
  {
    UINT32 aNodeIndex = aNode->Descendants[i].NodePointer;
    if (aNodeIndex < kDescendantEmptyValue)
      aNumNodes++;
    else if (aNodeIndex > kDescendantEmptyValue)
      aNumMatches++;
  }
  aNumMatches -= 1;
  if (aNumNodes + aNumMatches > 1)
  {
    aNode->Descendants[descendantIndex].MakeEmpty();
    return;
  }
  if(aNumNodes == 1)
  {
    UINT32 i;
    for (i = 0; i < kNumSubNodes; i++)
      if (aNode->Descendants[i].IsNode())
        break;
    UINT32 aNextNodeIndex = aNode->Descendants[i].NodePointer;
    CNodePointer aNextNode = &m_Nodes[aNextNodeIndex];
    aNextNode->NumSameBits += aNode->NumSameBits + kNumSubBits;
    *aNode = *aNextNode;

    aNextNode->NextFreeNode = m_FreeNode;
    m_FreeNode = aNextNodeIndex;
    return;
  }
  UINT32 aMatchPointer;
  for (i = 0; i < kNumSubNodes; i++)
    if (aNode->Descendants[i].IsMatch() && i != descendantIndex)
    {
      aMatchPointer = aNode->Descendants[i].MatchPointer;
      break;
    }
  aNode->NextFreeNode = m_FreeNode;
  m_FreeNode = *aNodePointerPointer;
  *aNodePointerPointer = aMatchPointer;
}
#endif

const UINT32 kNormalizeStartPos = (UINT32(1) << (kNumBitsInIndex)) - 
    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 &aDescendant, UINT32 aSubValue)
{
  if (aDescendant.IsEmpty())
    return;
  if (aDescendant.IsMatch())
    aDescendant.MatchPointer = aDescendant.MatchPointer - aSubValue;
  else
  {
    CNode &aNode = m_Nodes[aDescendant.NodePointer];
    aNode.LastMatch = aNode.LastMatch - aSubValue;
    for (UINT32 i = 0; i < kNumSubNodes; i++)
       NormalizeDescendant(aNode.Descendants[i], aSubValue);
  }
}

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

  for(UINT32 aHash = 0; aHash < kHash2Size; aHash++)
  {
    CDescendant &aDescendant = m_Hash2Descendants[aHash];
    if (aDescendant.MatchPointer != kDescendantsNotInitilized2)
    {
      UINT32 aBase = aHash << 8;
      for (UINT32 i = 0; i < 0x100; i++)
        NormalizeDescendant(m_HashDescendants[aBase + i], aSubValue);
    }
    if (aDescendant.MatchPointer < kMatchStartValue2)
      continue;
    aDescendant.MatchPointer = aDescendant.MatchPointer - aSubValue;
  }
  
  #else
  
  for(UINT32 aHash = 0; aHash < kHashSize; aHash++)
    NormalizeDescendant(m_HashDescendants[aHash], aSubValue);
  
  #endif

}

#else

void CPatricia::TestRemoveDescendant(CDescendant &aDescendant, UINT32 aLimitPos)
{
  CNode &aNode = m_Nodes[aDescendant.NodePointer];
  UINT32 aNumChilds = 0;
  UINT32 aChildIndex;
  for (UINT32 i = 0; i < kNumSubNodes; i++)
  {
    CDescendant &aDescendant2 = aNode.Descendants[i];
    if (aDescendant2.IsEmpty())
      continue;
    if (aDescendant2.IsMatch())
    {
      if (aDescendant2.MatchPointer < aLimitPos)
        aDescendant2.MakeEmpty();
      else
      {
        aNumChilds++;
        aChildIndex = i;
      }
    }
    else
    {
      TestRemoveDescendant(aDescendant2, aLimitPos);
      if (!aDescendant2.IsEmpty())
      {
        aNumChilds++;
        aChildIndex = i;
      }
    }
  }
  if (aNumChilds > 1)
    return;

  CIndex aNodePointerTemp = aDescendant.NodePointer;
  if (aNumChilds == 1)
  {
    const CDescendant &aDescendant2 = aNode.Descendants[aChildIndex];
    if (aDescendant2.IsNode())
      m_Nodes[aDescendant2.NodePointer].NumSameBits += aNode.NumSameBits + kNumSubBits;
    aDescendant = aDescendant2;
  }
  else
    aDescendant.MakeEmpty();
  aNode.NextFreeNode = m_FreeNode;
  m_FreeNode = aNodePointerTemp;
  m_NumUsedNodes--;
}

void CPatricia::RemoveNode(UINT32 anIndex)
{
  CNode &aNode = m_Nodes[anIndex];
  for (UINT32 i = 0; i < kNumSubNodes; i++)
  {
    CDescendant &aDescendant2 = aNode.Descendants[i];
    if (aDescendant2.IsNode())
      RemoveNode(aDescendant2.NodePointer);
  }
  aNode.NextFreeNode = m_FreeNode;
  m_FreeNode = anIndex;
  m_NumUsedNodes--;
}

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

void CPatricia::TestRemoveAndNormalizeDescendant(CDescendant &aDescendant, 
    UINT32 aLimitPos, UINT32 aSubValue)
{
  if (aDescendant.IsEmpty())
    return;
  if (aDescendant.IsMatch())
  {
    if (aDescendant.MatchPointer < aLimitPos)
      aDescendant.MakeEmpty();
    else
      aDescendant.MatchPointer = aDescendant.MatchPointer - aSubValue;
    return;
  }
  CNode &aNode = m_Nodes[aDescendant.NodePointer];
  UINT32 aNumChilds = 0;
  UINT32 aChildIndex;
  for (UINT32 i = 0; i < kNumSubNodes; i++)
  {
    CDescendant &aDescendant2 = aNode.Descendants[i];
    TestRemoveAndNormalizeDescendant(aDescendant2, aLimitPos, aSubValue);
    if (!aDescendant2.IsEmpty())
    {
      aNumChilds++;
      aChildIndex = i;
    }
  }
  if (aNumChilds > 1)
  {
    aNode.LastMatch = aNode.LastMatch - aSubValue;
    return;
  }

  CIndex aNodePointerTemp = aDescendant.NodePointer;
  if (aNumChilds == 1)
  {
    const CDescendant &aDescendant2 = aNode.Descendants[aChildIndex];
    if (aDescendant2.IsNode())
      m_Nodes[aDescendant2.NodePointer].NumSameBits += aNode.NumSameBits + kNumSubBits;
    aDescendant = aDescendant2;
  }
  else
    aDescendant.MakeEmpty();
  aNode.NextFreeNode = m_FreeNode;
  m_FreeNode = aNodePointerTemp;
  m_NumUsedNodes--;
}

void CPatricia::TestRemoveNodesAndNormalize()
{
  UINT32 aSubValue = _pos - _sizeHistory;
  UINT32 aLimitPos = kMatchStartValue + _pos - _sizeHistory + kNumHashBytes;
  CLZInWindow::ReduceOffsets(aSubValue);

  #ifdef __HASH_3
  
  UINT32 aLimitPos2 = kMatchStartValue2 + _pos - _sizeHistory + kNumHashBytes;
  for(UINT32 aHash = 0; aHash < kHash2Size; aHash++)
  {
    CDescendant &aDescendant = m_Hash2Descendants[aHash];
    if (aDescendant.MatchPointer != kDescendantsNotInitilized2)
    {
      UINT32 aBase = aHash << 8;
      for (UINT32 i = 0; i < 0x100; i++)
        TestRemoveAndNormalizeDescendant(m_HashDescendants[aBase + i], aLimitPos, aSubValue);
    }
    if (aDescendant.MatchPointer < kMatchStartValue2)
      continue;
    if (aDescendant.MatchPointer < aLimitPos2)
      aDescendant.MatchPointer = kDescendantEmptyValue2;
    else
      aDescendant.MatchPointer = aDescendant.MatchPointer - aSubValue;
  }
  
  #else

  for(UINT32 aHash = 0; aHash < kHashSize; aHash++)
    TestRemoveAndNormalizeDescendant(m_HashDescendants[aHash], aLimitPos, aSubValue);

  #endif
}

#endif

STDMETHODIMP_(BYTE) CPatricia::GetIndexByte(UINT32 anIndex)
{
  return CLZInWindow::GetIndexByte(anIndex);
}

STDMETHODIMP_(UINT32) CPatricia::GetMatchLen(UINT32 aIndex, UINT32 aBack, UINT32 aLimit)
{
  return CLZInWindow::GetMatchLen(aIndex, aBack, aLimit);
}

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

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

}