deflateencoder.cpp

7-Zip 3.11的源码

// DeflateEncoder.cpp

#include "StdAfx.h"

#include "DeflateEncoder.h"
#include "DeflateConst.h"

#include "Windows/Defs.h"
#include "Common/ComTry.h"
#include "../LZ/BinTree/BinTree3ZMain.h"

namespace NCompress {
namespace NDeflate {
namespace NEncoder {

class CMatchFinderException
{
public:
  HRESULT m_Result;
  CMatchFinderException(HRESULT result): m_Result (result) {}
};

static const int kValueBlockSize = 0x2000;

static const int kMaxCodeBitLength = 15;
static const int kMaxLevelBitLength = 7;

static const BYTE kFlagImm     = 0;
static const BYTE kFlagLenPos  = 4;

static const UINT32 kMaxUncompressedBlockSize = 0xFFFF; // test it !!!

static const UINT32 kBlockUncompressedSizeThreshold = 
    kMaxUncompressedBlockSize - kMatchMaxLen32 - kNumOpts;

static const int kNumGoodBacks = 0x10000; 

static BYTE kNoLiteralDummy = 13;
static BYTE kNoLenDummy = 13;
static BYTE kNoPosDummy = 6;

static BYTE g_LenSlots[kNumLenCombinations32];
static BYTE g_FastPos[1 << 9];

class CFastPosInit
{
public:
  CFastPosInit()
  {
    int i;
    for(i = 0; i < kLenTableSize; i++)
    {
      int c = kLenStart32[i];
      int j = 1 << kLenDirectBits32[i];
      for(int k = 0; k < j; k++, c++)
        g_LenSlots[c] = i;
    }
    
    const int kFastSlots = 18;
    int c = 0;
    for (BYTE slotFast = 0; slotFast < kFastSlots; slotFast++)
    {
      UINT32 k = (1 << kDistDirectBits[slotFast]);
      for (UINT32 j = 0; j < k; j++, c++)
        g_FastPos[c] = slotFast;
    }
  }
};

static CFastPosInit g_FastPosInit;


inline UINT32 GetPosSlot(UINT32 pos)
{
  //  for (UINT32 i = 1; pos >= kDistStart[i]; i++);
  //    return i - 1;
  if (pos < 0x200)
    return g_FastPos[pos];
  return g_FastPos[pos >> 8] + 16;
}

CCoder::CCoder(bool deflate64Mode):
  _deflate64Mode(deflate64Mode),
  m_MainCoder(kMainTableSize, 
      deflate64Mode ? kLenDirectBits64 : kLenDirectBits32, 
      kMatchNumber, kMaxCodeBitLength),
  m_DistCoder(deflate64Mode ? kDistTableSize64 : kDistTableSize32, kDistDirectBits, 0, kMaxCodeBitLength),
  m_LevelCoder(kLevelTableSize, kLevelDirectBits, 0, kMaxLevelBitLength),
  m_NumPasses(1),
  m_NumFastBytes(32),
  m_OnePosMatchesMemory(0),
  m_OnePosMatchesArray(0),
  m_MatchDistances(0),
  m_Created(false),
  m_Values(0)
{
  m_MatchMaxLen = deflate64Mode ? kMatchMaxLen64 : kMatchMaxLen32;
  m_NumLenCombinations = deflate64Mode ? kNumLenCombinations64 : 
    kNumLenCombinations32;
  m_LenStart = deflate64Mode ? kLenStart64 : kLenStart32;
  m_LenDirectBits = deflate64Mode ? kLenDirectBits64 : kLenDirectBits32;

  m_Values = new CCodeValue[kValueBlockSize + kNumOpts];
}

HRESULT CCoder::Create()
{
  COM_TRY_BEGIN
  m_MatchFinder.Create(
    _deflate64Mode ? kHistorySize64 : kHistorySize32, 
    kNumOpts + kNumGoodBacks, m_NumFastBytes, 
    m_MatchMaxLen - m_NumFastBytes);
  m_MatchLengthEdge = m_NumFastBytes + 1;

  if (m_NumPasses > 1)
  {
    m_OnePosMatchesMemory = new UINT16[kNumGoodBacks * (m_NumFastBytes + 1)];
    try
    {
      m_OnePosMatchesArray = new COnePosMatches[kNumGoodBacks];
    }
    catch(...)
    {
      delete []m_OnePosMatchesMemory;
      m_OnePosMatchesMemory = 0;
      throw;
    }
    UINT16 *goodBacksWordsCurrent = m_OnePosMatchesMemory;
    for(int i = 0; i < kNumGoodBacks; i++, goodBacksWordsCurrent += (m_NumFastBytes + 1))
      m_OnePosMatchesArray[i].Init(goodBacksWordsCurrent);
  }
  else
    m_MatchDistances = new UINT16[m_NumFastBytes + 1];
  return S_OK;
  COM_TRY_END
}

// ICompressSetEncoderProperties2
HRESULT CCoder::BaseSetEncoderProperties2(const PROPID *propIDs, 
    const PROPVARIANT *properties, UINT32 numProperties)
{
  for(UINT32 i = 0; i < numProperties; i++)
  {
    const PROPVARIANT &property = properties[i]; 
    switch(propIDs[i])
    {
      case NCoderPropID::kNumPasses:
        if (property.vt != VT_UI4)
          return E_INVALIDARG;
        m_NumPasses = property.ulVal;
        if(m_NumPasses == 0 || m_NumPasses > 255)
          return E_INVALIDARG;
        break;
      case NCoderPropID::kNumFastBytes:
        if (property.vt != VT_UI4)
          return E_INVALIDARG;
        m_NumFastBytes = property.ulVal;
        if(m_NumFastBytes < 3 || m_NumFastBytes > m_MatchMaxLen)
          return E_INVALIDARG;
        break;
      default:
        return E_INVALIDARG;
    }
  }
  return S_OK;
}
  
void CCoder::Free()
{
  if(m_NumPasses > 0)
  {
    if (m_NumPasses > 1)
    {
      delete []m_OnePosMatchesMemory;
      delete []m_OnePosMatchesArray;
    }
    else
      delete []m_MatchDistances;
  }
}

CCoder::~CCoder()
{
  Free();
  delete []m_Values;
}

void CCoder::ReadGoodBacks()
{
  UINT32 goodIndex;
  if (m_NumPasses > 1)
  {
    goodIndex = m_FinderPos % kNumGoodBacks;
    m_MatchDistances = m_OnePosMatchesArray[goodIndex].MatchDistances;
  }
  UINT32 distanceTmp[kMatchMaxLen32 + 1];
  UINT32 len = m_MatchFinder.GetLongestMatch(distanceTmp);
  for(UINT32 i = kMatchMinLen; i <= len; i++)
    m_MatchDistances[i] = distanceTmp[i];

  m_LongestMatchDistance = m_MatchDistances[len];
  if (len == m_NumFastBytes && m_NumFastBytes != m_MatchMaxLen)
    m_LongestMatchLength = len + m_MatchFinder.GetMatchLen(len, 
        m_LongestMatchDistance, m_MatchMaxLen - len);
  else
    m_LongestMatchLength = len;
  if (m_NumPasses > 1)
  {
    m_OnePosMatchesArray[goodIndex].LongestMatchDistance = UINT16(m_LongestMatchDistance);
    m_OnePosMatchesArray[goodIndex].LongestMatchLength = UINT16(m_LongestMatchLength);
  }
  HRESULT result = m_MatchFinder.MovePos();
  if (result != S_OK)
    throw CMatchFinderException(result);
  m_FinderPos++;
  m_AdditionalOffset++;
}

void CCoder::GetBacks(UINT32 pos)
{
  if(pos == m_FinderPos)
    ReadGoodBacks();
  else
  {
    if (m_NumPasses == 1)
    {
      if(pos + 1 == m_FinderPos) 
        return;
      throw 1932;   
    }
    else
    {
      UINT32 goodIndex = pos % kNumGoodBacks;
      m_MatchDistances = m_OnePosMatchesArray[goodIndex].MatchDistances;
      m_LongestMatchDistance = m_OnePosMatchesArray[goodIndex].LongestMatchDistance;
      m_LongestMatchLength = m_OnePosMatchesArray[goodIndex].LongestMatchLength;
    }
  }
}


void CCoder::MovePos(UINT32 num)
{
  if (m_NumPasses > 1)
  {
    for(UINT32 i = 0; i < num; i++)
      GetBacks(UINT32(m_BlockStartPostion + m_CurrentBlockUncompressedSize + i + 1));
  }
  else
  {
    for (;num > 0; num--)
    {
      m_MatchFinder.DummyLongestMatch();
      HRESULT result = m_MatchFinder.MovePos();
      if (result != S_OK)
        throw CMatchFinderException(result);
      m_FinderPos++;
      m_AdditionalOffset++;
    }
  }
}

static const UINT32 kIfinityPrice = 0xFFFFFFF;

UINT32 CCoder::Backward(UINT32 &backRes, UINT32 cur)
{
  m_OptimumEndIndex = cur;
  UINT32 posMem = m_Optimum[cur].PosPrev;
  UINT16 backMem = m_Optimum[cur].BackPrev;
  do
  {
    UINT32 posPrev = posMem;
    UINT16 backCur = backMem;
    backMem = m_Optimum[posPrev].BackPrev;
    posMem = m_Optimum[posPrev].PosPrev;
    m_Optimum[posPrev].BackPrev = backCur;
    m_Optimum[posPrev].PosPrev = cur;
    cur = posPrev;
  }
  while(cur > 0);
  backRes = m_Optimum[0].BackPrev;
  m_OptimumCurrentIndex  = m_Optimum[0].PosPrev;
  return m_OptimumCurrentIndex; 
}

UINT32 CCoder::GetOptimal(UINT32 &backRes)
{
  if(m_OptimumEndIndex != m_OptimumCurrentIndex)
  {
    UINT32 len = m_Optimum[m_OptimumCurrentIndex].PosPrev - m_OptimumCurrentIndex;
    backRes = m_Optimum[m_OptimumCurrentIndex].BackPrev;
    m_OptimumCurrentIndex = m_Optimum[m_OptimumCurrentIndex].PosPrev;
    return len;
  }
  m_OptimumCurrentIndex = 0;
  m_OptimumEndIndex = 0;
  
  GetBacks(UINT32(m_BlockStartPostion + m_CurrentBlockUncompressedSize));

  UINT32 lenMain = m_LongestMatchLength;
  UINT32 backMain = m_LongestMatchDistance;

  if(lenMain < kMatchMinLen)
    return 1;
  if(lenMain >= m_MatchLengthEdge)
  {
    backRes = backMain; 
    MovePos(lenMain - 1);
    return lenMain;
  }
  m_Optimum[1].Price = m_LiteralPrices[m_MatchFinder.GetIndexByte(0 - m_AdditionalOffset)];
  m_Optimum[1].PosPrev = 0;

  m_Optimum[2].Price = kIfinityPrice;
  m_Optimum[2].PosPrev = 1;

  for(UINT32 i = kMatchMinLen; i <= lenMain; i++)
  {
    m_Optimum[i].PosPrev = 0;
    m_Optimum[i].BackPrev = m_MatchDistances[i];
    m_Optimum[i].Price = m_LenPrices[i - kMatchMinLen] + m_PosPrices[GetPosSlot(m_MatchDistances[i])];
  }


  UINT32 cur = 0;
  UINT32 lenEnd = lenMain;
  while(true)
  {
    cur++;
    if(cur == lenEnd)  
      return Backward(backRes, cur);
    GetBacks(UINT32(m_BlockStartPostion + m_CurrentBlockUncompressedSize + cur));
    UINT32 newLen = m_LongestMatchLength;
    if(newLen >= m_MatchLengthEdge)
      return Backward(backRes, cur);
    
    UINT32 curPrice = m_Optimum[cur].Price; 
    UINT32 curAnd1Price = curPrice +
        m_LiteralPrices[m_MatchFinder.GetIndexByte(cur - m_AdditionalOffset)];
    COptimal &optimum = m_Optimum[cur + 1];
    if (curAnd1Price < optimum.Price) 
    {
      optimum.Price = curAnd1Price;
      optimum.PosPrev = cur;
    }
    if (newLen < kMatchMinLen)
      continue;
    if(cur + newLen > lenEnd)
    {
      if (cur + newLen > kNumOpts - 1)
        newLen = kNumOpts - 1 - cur;
      UINT32 lenEndNew = cur + newLen;
      if (lenEnd < lenEndNew)
      {
        for(UINT32 i = lenEnd + 1; i <= lenEndNew; i++)
          m_Optimum[i].Price = kIfinityPrice;
        lenEnd = lenEndNew;
      }
    }       
    for(UINT32 lenTest = kMatchMinLen; lenTest <= newLen; lenTest++)
    {
      UINT16 curBack = m_MatchDistances[lenTest];
      UINT32 curAndLenPrice = curPrice + 
          m_LenPrices[lenTest - kMatchMinLen] + m_PosPrices[GetPosSlot(curBack)];
      COptimal &optimum = m_Optimum[cur + lenTest];
      if (curAndLenPrice < optimum.Price) 
      {
        optimum.Price = curAndLenPrice;
        optimum.PosPrev = cur;
        optimum.BackPrev = curBack;
      }
    }
  }
}


void CCoder::InitStructures()
{
  memset(m_LastLevels, 0, kMaxTableSize64);

  m_ValueIndex = 0;
  m_OptimumEndIndex = 0;
  m_OptimumCurrentIndex = 0;
  m_AdditionalOffset = 0;

  m_BlockStartPostion = 0;
  m_CurrentBlockUncompressedSize = 0;

  m_MainCoder.StartNewBlock();
  m_DistCoder.StartNewBlock();
 
  UINT32 i;
  for(i = 0; i < 256; i++)