deflateencoder.cpp

著名的7zip的压缩算法,压缩比最高,但是压缩时间也比较长!

        else
          LevelCoder.AddSymbol(curLen);
    else if (curLen != 0) 
    {
      if (curLen != prevLen) 
      {
        if (outStream != 0)
          LevelCoder.CodeOneValue(outStream, curLen);
        else
          LevelCoder.AddSymbol(curLen);
        count--;
      }
      if (outStream != 0)
      {
        LevelCoder.CodeOneValue(outStream, kTableLevelRepNumber);
        outStream->WriteBits(count - 3, 2);
      }
      else
        LevelCoder.AddSymbol(kTableLevelRepNumber);
    } 
    else if (count <= 10) 
      if (outStream != 0)
      {
        LevelCoder.CodeOneValue(outStream, kTableLevel0Number);
        outStream->WriteBits(count - 3, 3);
      }
      else
        LevelCoder.AddSymbol(kTableLevel0Number);
    else 
      if (outStream != 0)
      {
        LevelCoder.CodeOneValue(outStream, kTableLevel0Number2);
        outStream->WriteBits(count - 11, 7);
      }
      else
        LevelCoder.AddSymbol(kTableLevel0Number2);

    count = 0; 
    prevLen = curLen;
    
    if (nextLen == 0) 
    {
      maxCount = 138;
      minCount = 3;
    } 
    else if (curLen == nextLen) 
    {
      maxCount = 6;
      minCount = 3;
    } 
    else 
    {
      maxCount = 7;
      minCount = 4;
    }
  }
}

void CCoder::MakeTables()
{
  MainCoder.BuildTree(m_NewLevels.litLenLevels);
  DistCoder.BuildTree(m_NewLevels.distLevels);
  MainCoder.ReverseBits();
  DistCoder.ReverseBits();
}

UInt32 CCoder::GetLzBlockPrice()
{
  LevelCoder.StartNewBlock();
  
  m_NumLitLenLevels = kMainTableSize;
  while(m_NumLitLenLevels > kNumLitLenCodesMin && m_NewLevels.litLenLevels[m_NumLitLenLevels - 1] == 0)
    m_NumLitLenLevels--;
  
  m_NumDistLevels = kDistTableSize64;
  while(m_NumDistLevels > kNumDistCodesMin && m_NewLevels.distLevels[m_NumDistLevels - 1] == 0)
    m_NumDistLevels--;
  
  CodeLevelTable(0, m_NewLevels.litLenLevels, m_NumLitLenLevels);
  CodeLevelTable(0, m_NewLevels.distLevels, m_NumDistLevels);
  
  Byte levelLevels[kLevelTableSize];
  LevelCoder.BuildTree(levelLevels);
  LevelCoder.ReverseBits();
  
  m_NumLevelCodes = kNumLevelCodesMin;
  for (UInt32 i = 0; i < kLevelTableSize; i++)
  {
    Byte level = levelLevels[kCodeLengthAlphabetOrder[i]]; 
    if (level > 0 && i >= m_NumLevelCodes)
      m_NumLevelCodes = i + 1;
    m_LevelLevels[i] = level;
  }
  
  return MainCoder.GetBlockBitLength() + DistCoder.GetBlockBitLength() + LevelCoder.GetBlockBitLength() +
      kNumLenCodesFieldSize + kNumDistCodesFieldSize + kNumLevelCodesFieldSize +
      m_NumLevelCodes * kLevelFieldSize + kFinalBlockFieldSize + kBlockTypeFieldSize;
}

void CCoder::TryBlock(bool staticMode)
{
  MainCoder.StartNewBlock();
  DistCoder.StartNewBlock();
  m_ValueIndex = 0;
  UInt32 blockSize = BlockSizeRes;
  BlockSizeRes = 0;
  while(true)
  {
    if (m_OptimumCurrentIndex == m_OptimumEndIndex)
    {
      if (m_Pos >= kMatchArrayLimit || BlockSizeRes >= blockSize || !m_SecondPass && 
          ((m_MatchFinder->GetNumAvailableBytes() == 0) || m_ValueIndex >= m_ValueBlockSize))
        break;
    }
    UInt32 pos;
    UInt32 len = GetOptimal(pos);
    CCodeValue &codeValue = m_Values[m_ValueIndex++];
    if (len >= kMatchMinLen)
    {
      UInt32 newLen = len - kMatchMinLen;
      codeValue.Len = (UInt16)newLen;
      MainCoder.AddSymbol(kSymbolMatch + g_LenSlots[newLen]);
      codeValue.Pos = (UInt16)pos;
      DistCoder.AddSymbol(GetPosSlot(pos));
    }
    else
    {
      Byte b = m_MatchFinder->GetIndexByte(0 - m_AdditionalOffset);
      MainCoder.AddSymbol(b);
      codeValue.SetAsLiteral();
      codeValue.Pos = b;
    }
    m_AdditionalOffset -= len;
    BlockSizeRes += len;
  }
  MainCoder.AddSymbol(kSymbolEndOfBlock);
  if (!staticMode)
  {
    MakeTables();
    SetPrices(m_NewLevels);
  }
  m_AdditionalOffset += BlockSizeRes;
  m_SecondPass = true;
}

void CCoder::SetPrices(const CLevels &levels)
{
  UInt32 i;
  for(i = 0; i < 256; i++)
  {
    Byte price = levels.litLenLevels[i];
    m_LiteralPrices[i] = ((price != 0) ? price : kNoLiteralStatPrice);
  }
  
  for(i = 0; i < m_NumLenCombinations; i++)
  {
    UInt32 slot = g_LenSlots[i];
    Byte price = levels.litLenLevels[kSymbolMatch + slot];
    m_LenPrices[i] = ((price != 0) ? price : kNoLenStatPrice) + m_LenDirectBits[slot];
  }
  
  for(i = 0; i < kDistTableSize64; i++)
  {
    Byte price = levels.distLevels[i];
    m_PosPrices[i] = ((price != 0) ? price: kNoPosStatPrice) + kDistDirectBits[i];
  }
}

void CCoder::WriteBlock()
{
  for (UInt32 i = 0; i < m_ValueIndex; i++)
  {
    const CCodeValue &codeValue = m_Values[i];
    if (codeValue.IsLiteral())
      MainCoder.CodeOneValue(&m_OutStream, codeValue.Pos);
    else
    {
      UInt32 len = codeValue.Len;
      UInt32 lenSlot = g_LenSlots[len];
      MainCoder.CodeOneValue(&m_OutStream, kSymbolMatch + lenSlot);
      m_OutStream.WriteBits(len - m_LenStart[lenSlot], m_LenDirectBits[lenSlot]);
      UInt32 dist = codeValue.Pos;
      UInt32 posSlot = GetPosSlot(dist);
      DistCoder.CodeOneValue(&m_OutStream, posSlot);
      m_OutStream.WriteBits(dist - kDistStart[posSlot], kDistDirectBits[posSlot]);
    }
  }
  MainCoder.CodeOneValue(&m_OutStream, kSymbolEndOfBlock);
}

void CCoder::WriteDynBlock(bool finalBlock)
{
  m_OutStream.WriteBits((finalBlock ? NFinalBlockField::kFinalBlock: NFinalBlockField::kNotFinalBlock), kFinalBlockFieldSize);
  m_OutStream.WriteBits(NBlockType::kDynamicHuffman, kBlockTypeFieldSize);
  m_OutStream.WriteBits(m_NumLitLenLevels - kNumLitLenCodesMin, kNumLenCodesFieldSize);
  m_OutStream.WriteBits(m_NumDistLevels - kNumDistCodesMin, kNumDistCodesFieldSize);
  m_OutStream.WriteBits(m_NumLevelCodes - kNumLevelCodesMin, kNumLevelCodesFieldSize);
      
  for (UInt32 i = 0; i < m_NumLevelCodes; i++)
    m_OutStream.WriteBits(m_LevelLevels[i], kLevelFieldSize);
      
  CodeLevelTable(&m_OutStream, m_NewLevels.litLenLevels, m_NumLitLenLevels);
  CodeLevelTable(&m_OutStream, m_NewLevels.distLevels, m_NumDistLevels);

  WriteBlock();
}

void CCoder::WriteFixedBlock(bool finalBlock)
{
  int i;
  for (i = 0; i < kFixedMainTableSize; i++)
    MainCoder.SetFreq(i, (UInt32)1 << (kNumHuffmanBits - m_NewLevels.litLenLevels[i]));
  for (i = 0; i < kFixedDistTableSize; i++)
    DistCoder.SetFreq(i, (UInt32)1 << (kNumHuffmanBits - m_NewLevels.distLevels[i]));
  MakeTables();

  m_OutStream.WriteBits((finalBlock ? NFinalBlockField::kFinalBlock: NFinalBlockField::kNotFinalBlock), kFinalBlockFieldSize);
  m_OutStream.WriteBits(NBlockType::kFixedHuffman, kBlockTypeFieldSize);
  WriteBlock();
}

static UInt32 GetStorePrice(UInt32 blockSize, int bitPosition)
{
  UInt32 price = 0;
  do
  {
    UInt32 nextBitPosition = (bitPosition + kFinalBlockFieldSize + kBlockTypeFieldSize) & 7;
    int numBitsForAlign = nextBitPosition > 0 ? (8 - nextBitPosition): 0;
    UInt32 curBlockSize = (blockSize < (1 << 16)) ? blockSize : (1 << 16) - 1;
    price += kFinalBlockFieldSize + kBlockTypeFieldSize + numBitsForAlign + (2 + 2) * 8 + curBlockSize * 8;
    bitPosition = 0;
    blockSize -= curBlockSize;
  }
  while(blockSize != 0);
  return price;
}

void CCoder::WriteStoreBlock(UInt32 blockSize, UInt32 additionalOffset, bool finalBlock)
{
  do
  {
    UInt32 curBlockSize = (blockSize < (1 << 16)) ? blockSize : (1 << 16) - 1;
    blockSize -= curBlockSize;
    m_OutStream.WriteBits((finalBlock && (blockSize == 0) ? NFinalBlockField::kFinalBlock: NFinalBlockField::kNotFinalBlock), kFinalBlockFieldSize);
    m_OutStream.WriteBits(NBlockType::kStored, kBlockTypeFieldSize);
    m_OutStream.FlushByte();
    m_OutStream.WriteBits((UInt16)curBlockSize, kStoredBlockLengthFieldSize);
    m_OutStream.WriteBits((UInt16)~curBlockSize, kStoredBlockLengthFieldSize);
    const Byte *data = m_MatchFinder->GetPointerToCurrentPos() - additionalOffset;
    for(UInt32 i = 0; i < curBlockSize; i++)
      m_OutStream.WriteByte(data[i]);
    additionalOffset -= curBlockSize;
  }
  while(blockSize != 0);
}

UInt32 CCoder::TryDynBlock(int tableIndex, UInt32 numPasses)
{
  CTables &t = m_Tables[tableIndex];
  BlockSizeRes = t.BlockSizeRes;
  m_Pos = t.m_Pos;
  SetPrices(t);

  for (UInt32 p = 0; p < numPasses; p++)
  {
    UInt32 posTemp = m_Pos;
    TryBlock(false);
    if (p != numPasses - 1)
      m_Pos = posTemp;
  }
  const UInt32 lzPrice = GetLzBlockPrice();
  (CLevels &)t = m_NewLevels;
  return lzPrice;
}

UInt32 CCoder::TryFixedBlock(int tableIndex)
{
  CTables &t = m_Tables[tableIndex];
  BlockSizeRes = t.BlockSizeRes;
  m_Pos = t.m_Pos;
  m_NewLevels.SetFixedLevels();
  SetPrices(m_NewLevels);

  TryBlock(true);
  return kFinalBlockFieldSize + kBlockTypeFieldSize +
      MainCoder.GetPrice(m_NewLevels.litLenLevels) + 
      DistCoder.GetPrice(m_NewLevels.distLevels);
}

UInt32 CCoder::GetBlockPrice(int tableIndex, int numDivPasses)
{
  CTables &t = m_Tables[tableIndex];
  t.StaticMode = false;
  UInt32 price = TryDynBlock(tableIndex, m_NumPasses);
  t.BlockSizeRes = BlockSizeRes;
  UInt32 numValues = m_ValueIndex;
  UInt32 posTemp = m_Pos;
  UInt32 additionalOffsetEnd = m_AdditionalOffset;
  
  if (m_CheckStatic && m_ValueIndex <= kFixedHuffmanCodeBlockSizeMax)
  {
    const UInt32 fixedPrice = TryFixedBlock(tableIndex);
    if (t.StaticMode = (fixedPrice < price))
      price = fixedPrice;
  }

  const UInt32 storePrice = GetStorePrice(BlockSizeRes, 0); // bitPosition
  if (t.StoreMode = (storePrice <= price))
    price = storePrice;

  t.UseSubBlocks = false;

  if (numDivPasses > 1 && numValues >= kDivideCodeBlockSizeMin)
  {
    CTables &t0 = m_Tables[(tableIndex << 1)];
    (CLevels &)t0 = t;
    t0.BlockSizeRes = t.BlockSizeRes >> 1;
    t0.m_Pos = t.m_Pos;
    UInt32 subPrice = GetBlockPrice((tableIndex << 1), numDivPasses - 1);

    UInt32 blockSize2 = t.BlockSizeRes - t0.BlockSizeRes;
    if (t0.BlockSizeRes >= kDivideBlockSizeMin && blockSize2 >= kDivideBlockSizeMin)
    {
      CTables &t1 = m_Tables[(tableIndex << 1) + 1];
      (CLevels &)t1 = t;
      t1.BlockSizeRes = blockSize2;
      t1.m_Pos = m_Pos;
      m_AdditionalOffset -= t0.BlockSizeRes;
      subPrice += GetBlockPrice((tableIndex << 1) + 1, numDivPasses - 1);
      if (t.UseSubBlocks = (subPrice < price))
        price = subPrice;
    }
  }
  m_AdditionalOffset = additionalOffsetEnd;
  m_Pos = posTemp;
  return price;
}

void CCoder::CodeBlock(int tableIndex, bool finalBlock)
{
  CTables &t = m_Tables[tableIndex];
  if (t.UseSubBlocks)
  {
    CodeBlock((tableIndex << 1), false);
    CodeBlock((tableIndex << 1) + 1, finalBlock);
  }
  else
  {
    if (t.StoreMode)
      WriteStoreBlock(t.BlockSizeRes, m_AdditionalOffset, finalBlock);
    else
      if (t.StaticMode)
      {
        TryFixedBlock(tableIndex);
        WriteFixedBlock(finalBlock);
      }
      else 
      {
        if (m_NumDivPasses > 1 || m_CheckStatic)
          TryDynBlock(tableIndex, 1);
        WriteDynBlock(finalBlock);
      }
    m_AdditionalOffset -= t.BlockSizeRes;
  }
}

HRESULT CCoder::CodeReal(ISequentialInStream *inStream,
    ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize,
    ICompressProgressInfo *progress)
{
  m_CheckStatic = (m_NumPasses != 1 || m_NumDivPasses != 1);
  m_IsMultiPass = (m_CheckStatic || (m_NumPasses != 1 || m_NumDivPasses != 1));

  RINOK(Create());

  m_ValueBlockSize = (1 << 13) + (1 << 12) * m_NumDivPasses;

  UInt64 nowPos = 0;

  RINOK(m_MatchFinder->SetStream(inStream));
  RINOK(m_MatchFinder->Init());
  m_OutStream.SetStream(outStream);
  m_OutStream.Init();

  CCoderReleaser coderReleaser(this);

  m_OptimumEndIndex = m_OptimumCurrentIndex = 0;

  CTables &t = m_Tables[1];
  t.m_Pos = 0;
  t.InitStructures();

  m_AdditionalOffset = 0;
  do
  {
    t.BlockSizeRes = kBlockUncompressedSizeThreshold;
    m_SecondPass = false;
    GetBlockPrice(1, m_NumDivPasses);
    CodeBlock(1, m_MatchFinder->GetNumAvailableBytes() == 0);
    nowPos += m_Tables[1].BlockSizeRes;
    if (progress != NULL)
    {
      UInt64 packSize = m_OutStream.GetProcessedSize();
      RINOK(progress->SetRatioInfo(&nowPos, &packSize));
    }
  }
  while(m_MatchFinder->GetNumAvailableBytes() != 0);
  return m_OutStream.Flush();
}

HRESULT CCoder::BaseCode(ISequentialInStream *inStream,
    ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize,
    ICompressProgressInfo *progress)
{
  try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
  catch(CMatchFinderException &e) { return e.ErrorCode; }
  catch(const COutBufferException &e) { return e.ErrorCode; }
  catch(...) { return E_FAIL; }
}

STDMETHODIMP CCOMCoder::Code(ISequentialInStream *inStream,
    ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize,
    ICompressProgressInfo *progress)
  { return BaseCode(inStream, outStream, inSize, outSize, progress); }

STDMETHODIMP CCOMCoder::SetCoderProperties(const PROPID *propIDs, 
    const PROPVARIANT *properties, UInt32 numProperties)
  { return BaseSetEncoderProperties2(propIDs, properties, numProperties); }

STDMETHODIMP CCOMCoder64::Code(ISequentialInStream *inStream,
    ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize,
    ICompressProgressInfo *progress)
  { return BaseCode(inStream, outStream, inSize, outSize, progress); }

STDMETHODIMP CCOMCoder64::SetCoderProperties(const PROPID *propIDs, 
    const PROPVARIANT *properties, UInt32 numProperties)
  { return BaseSetEncoderProperties2(propIDs, properties, numProperties); }

}}}