deflateencoder.cpp

来自「由7-zip提供的压缩、解压缩程序」· C++ 代码 · 共 882 行 · 第 1/2 页

// DeflateEncoder.cpp

#include "StdAfx.h"

#include "DeflateEncoder.h"

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

namespace NCompress {
namespace NDeflate {
namespace NEncoder {

const int kNumDivPassesMax = 10; // [0, 16); ratio/speed/ram tradeoff; use big value for better compression ratio.
const UInt32 kNumTables = (1 << kNumDivPassesMax);

static UInt32 kFixedHuffmanCodeBlockSizeMax = (1 << 8); // [0, (1 << 32)); ratio/speed tradeoff; use big value for better compression ratio.
static UInt32 kDivideCodeBlockSizeMin = (1 << 6); // [1, (1 << 32)); ratio/speed tradeoff; use small value for better compression ratio.
static UInt32 kDivideBlockSizeMin = (1 << 6); // [1, (1 << 32)); ratio/speed tradeoff; use small value for better compression ratio.

static const UInt32 kMaxUncompressedBlockSize = ((1 << 16) - 1) * 1; // [1, (1 << 32))
static const UInt32 kMatchArraySize = kMaxUncompressedBlockSize * 10; // [kMatchMaxLen * 2, (1 << 32))
static const UInt32 kMatchArrayLimit = kMatchArraySize - kMatchMaxLen * 4 * sizeof(UInt16);
static const UInt32 kBlockUncompressedSizeThreshold = kMaxUncompressedBlockSize - 
    kMatchMaxLen - kNumOpts;

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

struct CMatchFinderException
{
  HRESULT ErrorCode;
  CMatchFinderException(HRESULT errorCode): ErrorCode(errorCode) {}
};

static Byte kNoLiteralStatPrice = 13;
static Byte kNoLenStatPrice = 13;
static Byte kNoPosStatPrice = 6;

static Byte g_LenSlots[kNumLenSymbolsMax];
static Byte g_FastPos[1 << 9];

class CFastPosInit
{
public:
  CFastPosInit()
  {
    int i;
    for(i = 0; i < kNumLenSlots; i++)
    {
      int c = kLenStart32[i];
      int j = 1 << kLenDirectBits32[i];
      for(int k = 0; k < j; k++, c++)
        g_LenSlots[c] = (Byte)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)
{
  if (pos < 0x200)
    return g_FastPos[pos];
  return g_FastPos[pos >> 8] + 16;
}

CCoder::CCoder(bool deflate64Mode):
  m_Deflate64Mode(deflate64Mode),
  m_NumPasses(1),
  m_NumDivPasses(1),
  m_NumFastBytes(32),
  m_OnePosMatchesMemory(0),
  m_DistanceMemory(0),
  m_Created(false),
  m_Values(0),
  m_Tables(0),
  m_MatchFinderCycles(0),
  m_SetMfPasses(0)
{
  m_MatchMaxLen = deflate64Mode ? kMatchMaxLen64 : kMatchMaxLen32;
  m_NumLenCombinations = deflate64Mode ? kNumLenSymbols64 : kNumLenSymbols32;
  m_LenStart = deflate64Mode ? kLenStart64 : kLenStart32;
  m_LenDirectBits = deflate64Mode ? kLenDirectBits64 : kLenDirectBits32;
}

HRESULT CCoder::Create()
{
  COM_TRY_BEGIN
  if (!m_MatchFinder)
  {
    NBT3Z::CMatchFinder *matchFinderSpec = new NBT3Z::CMatchFinder;
    m_SetMfPasses = matchFinderSpec;
    m_MatchFinder = matchFinderSpec;
    if (m_MatchFinder == 0)
      return E_OUTOFMEMORY;
  }
  if (m_Values == 0)
  {
    m_Values = (CCodeValue *)MyAlloc((kMaxUncompressedBlockSize) * sizeof(CCodeValue));
    if (m_Values == 0)
      return E_OUTOFMEMORY;
  }
  if (m_Tables == 0)
  {
    m_Tables = (CTables *)MyAlloc((kNumTables) * sizeof(CTables));
    if (m_Tables == 0)
      return E_OUTOFMEMORY;
  }

  if (m_IsMultiPass)
  {
    if (m_OnePosMatchesMemory == 0)
    {
      m_OnePosMatchesMemory = (UInt16 *)::MidAlloc(kMatchArraySize * sizeof(UInt16));
      if (m_OnePosMatchesMemory == 0)
        return E_OUTOFMEMORY;
    }
  }
  else
  {
    if (m_DistanceMemory == 0)
    {
      m_DistanceMemory = (UInt16 *)MyAlloc((kMatchMaxLen + 2) * 2 * sizeof(UInt16));
      if (m_DistanceMemory == 0)
        return E_OUTOFMEMORY;
      m_MatchDistances = m_DistanceMemory;
    }
  }

  if (!m_Created)
  {
    RINOK(m_MatchFinder->Create(m_Deflate64Mode ? kHistorySize64 : kHistorySize32, 
      kNumOpts + kMaxUncompressedBlockSize, m_NumFastBytes, m_MatchMaxLen - m_NumFastBytes));
    if (!m_OutStream.Create(1 << 20))
      return E_OUTOFMEMORY;
    if (!MainCoder.Create(kFixedMainTableSize, m_LenDirectBits, kSymbolMatch, kMaxCodeBitLength))
      return E_OUTOFMEMORY;
    if (!DistCoder.Create(kDistTableSize64, kDistDirectBits, 0, kMaxCodeBitLength))
      return E_OUTOFMEMORY;
    if (!LevelCoder.Create(kLevelTableSize, kLevelDirectBits, kTableDirectLevels, kMaxLevelBitLength))
      return E_OUTOFMEMORY;
  }
  if (m_MatchFinderCycles != 0 && m_SetMfPasses != 0)
    m_SetMfPasses->SetNumPasses(m_MatchFinderCycles);
  m_Created = true;
  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 &prop = properties[i]; 
    switch(propIDs[i])
    {
      case NCoderPropID::kNumPasses:
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        m_NumDivPasses = prop.ulVal;
        if (m_NumDivPasses == 0)
          m_NumDivPasses = 1;
        if (m_NumDivPasses == 1)
          m_NumPasses = 1;
        else if (m_NumDivPasses <= kNumDivPassesMax)
          m_NumPasses = 2;
        else
        {
          m_NumPasses = 2 + (m_NumDivPasses - kNumDivPassesMax);
          m_NumDivPasses = kNumDivPassesMax;
        }
        break;
      case NCoderPropID::kNumFastBytes:
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        m_NumFastBytes = prop.ulVal;
        if(m_NumFastBytes < kMatchMinLen || m_NumFastBytes > m_MatchMaxLen)
          return E_INVALIDARG;
        break;
      case NCoderPropID::kMatchFinderCycles:
      {
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        m_MatchFinderCycles = prop.ulVal;
        break;
      }
      default:
        return E_INVALIDARG;
    }
  }
  return S_OK;
}
  
void CCoder::Free()
{
  ::MidFree(m_OnePosMatchesMemory);
  m_OnePosMatchesMemory = 0;
  ::MyFree(m_DistanceMemory);
  m_DistanceMemory = 0;
  ::MyFree(m_Values);
  m_Values = 0;
  ::MyFree(m_Tables);
  m_Tables = 0;
}

CCoder::~CCoder()
{
  Free();
}

void CCoder::GetMatches()
{
  if (m_IsMultiPass)
  {
    m_MatchDistances = m_OnePosMatchesMemory + m_Pos;
    if (m_SecondPass)
    {
      m_Pos += *m_MatchDistances + 1;
      return;
    }
  }

  UInt32 distanceTmp[kMatchMaxLen * 2 + 3];
  
  HRESULT result = m_MatchFinder->GetMatches(distanceTmp);
  if (result != S_OK)
    throw CMatchFinderException(result);
  UInt32 numPairs = distanceTmp[0];

  *m_MatchDistances = (UInt16)numPairs;
   
  if (numPairs > 0)
  {
    UInt32 i = 1;
    for(i = 1; i < numPairs; i += 2)
    {
      m_MatchDistances[i] = (UInt16)distanceTmp[i];
      m_MatchDistances[i + 1] = (UInt16)distanceTmp[i + 1];
    }
    UInt32 len = distanceTmp[1 + numPairs - 2];
    if (len == m_NumFastBytes && m_NumFastBytes != m_MatchMaxLen)
      m_MatchDistances[i - 2] = (UInt16)(len + m_MatchFinder->GetMatchLen(len - 1, 
      distanceTmp[1 + numPairs - 1], m_MatchMaxLen - len));
  }
  if (m_IsMultiPass)
    m_Pos += numPairs + 1;
  if (!m_SecondPass)
    m_AdditionalOffset++;
}

void CCoder::MovePos(UInt32 num)
{
  if (!m_SecondPass && num > 0)
  {
    HRESULT result = m_MatchFinder->Skip(num);
    if (result != S_OK)
      throw CMatchFinderException(result);
    m_AdditionalOffset += num;
  }
}

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 = (UInt16)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 = m_OptimumEndIndex = 0;
  
  GetMatches();

  UInt32 numDistancePairs = m_MatchDistances[0];
  if(numDistancePairs == 0)
    return 1;

  const UInt16 *matchDistances = m_MatchDistances + 1;
  UInt32 lenMain = matchDistances[numDistancePairs - 2];

  if(lenMain > m_NumFastBytes)
  {
    backRes = matchDistances[numDistancePairs - 1]; 
    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;


  UInt32 offs = 0;
  for(UInt32 i = kMatchMinLen; i <= lenMain; i++)
  {
    UInt32 distance = matchDistances[offs + 1];
    m_Optimum[i].PosPrev = 0;
    m_Optimum[i].BackPrev = distance;
    m_Optimum[i].Price = m_LenPrices[i - kMatchMinLen] + m_PosPrices[GetPosSlot(distance)];
    if (i == matchDistances[offs])
      offs += 2;
  }

  UInt32 cur = 0;
  UInt32 lenEnd = lenMain;
  while(true)
  {
    ++cur;
    if(cur == lenEnd || cur == kNumOptsBase || m_Pos >= kMatchArrayLimit)  
      return Backward(backRes, cur);
    GetMatches();
    matchDistances = m_MatchDistances + 1;

    UInt32 numDistancePairs = m_MatchDistances[0];
    UInt32 newLen = 0;
    if(numDistancePairs != 0)
    { 
      newLen = matchDistances[numDistancePairs - 2];
      if(newLen > m_NumFastBytes)
      {
        UInt32 len = Backward(backRes, cur);
        m_Optimum[cur].BackPrev = matchDistances[numDistancePairs - 1];
        m_Optimum[cur].PosPrev = m_OptimumEndIndex = cur + newLen;
        MovePos(newLen - 1);
        return len;
      }
    }
    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 = (UInt16)cur;
    }
    if(numDistancePairs == 0)
      continue;
    while(lenEnd < cur + newLen)
      m_Optimum[++lenEnd].Price = kIfinityPrice;
    offs = 0;
    UInt32 distance = matchDistances[offs + 1];
    curPrice += m_PosPrices[GetPosSlot(distance)];
    for(UInt32 lenTest = kMatchMinLen; ; lenTest++)
    {
      UInt32 curAndLenPrice = curPrice + m_LenPrices[lenTest - kMatchMinLen];
      COptimal &optimum = m_Optimum[cur + lenTest];
      if (curAndLenPrice < optimum.Price) 
      {
        optimum.Price = curAndLenPrice;
        optimum.PosPrev = (UInt16)cur;
        optimum.BackPrev = distance;
      }
      if (lenTest == matchDistances[offs])
      {
        offs += 2;
        if (offs == numDistancePairs)
          break;
        curPrice -= m_PosPrices[GetPosSlot(distance)];
        distance = matchDistances[offs + 1];
        curPrice += m_PosPrices[GetPosSlot(distance)];
      }
    }
  }
}

void CTables::InitStructures()
{
  UInt32 i;
  for(i = 0; i < 256; i++)
    litLenLevels[i] = 8;
  litLenLevels[i++] = 13;
  for(;i < kFixedMainTableSize; i++)
    litLenLevels[i] = 5;
  for(i = 0; i < kFixedDistTableSize; i++)
    distLevels[i] = 5;
}

void CCoder::CodeLevelTable(NStream::NLSBF::CEncoder *outStream, const Byte *levels, int numLevels)
{
  int prevLen = 0xFF;
  int nextLen = levels[0];
  int count = 0;
  int maxCount = 7;
  int minCount = 4;
  if (nextLen == 0) 
  {
    maxCount = 138;
    minCount = 3;
  }
  for (int n = 0; n < numLevels; n++) 
  {
    int curLen = nextLen; 
    nextLen = (n < numLevels - 1) ? levels[n + 1] : 0xFF;
    count++;
    if (count < maxCount && curLen == nextLen) 
      continue;
    
    if (count < minCount) 
      for(int i = 0; i < count; i++) 
        if (outStream != 0)
          LevelCoder.CodeOneValue(outStream, curLen);