deflateencoder.cpp

压缩软件源码

    m_LenPrices[i] = (Byte)(5 + m_LenDirectBits[g_LenSlots[i]]); // test it
  for(i = 0; i < kDistTableSize64; i++)
    m_PosPrices[i] = (Byte)(5 + kDistDirectBits[i]);
}

void CCoder::WriteBlockData(bool writeMode, bool finalBlock)
{
  m_MainCoder.AddSymbol(kReadTableNumber);
  int method = WriteTables(writeMode, finalBlock);
  
  if (writeMode)
  {
    if(method == NBlockType::kStored)
    {
      for(UInt32 i = 0; i < m_CurrentBlockUncompressedSize; i++)
      {
        Byte b = m_MatchFinder->GetIndexByte(i - m_AdditionalOffset - 
              m_CurrentBlockUncompressedSize);
        m_OutStream.WriteBits(b, 8);
      }
    }
    else
    {
      for (UInt32 i = 0; i < m_ValueIndex; i++)
      {
        if (m_Values[i].Flag == kFlagImm)
          m_MainCoder.CodeOneValue(&m_ReverseOutStream, m_Values[i].Imm);
        else if (m_Values[i].Flag == kFlagLenPos)
        {
          UInt32 len = m_Values[i].Len;
          UInt32 lenSlot = g_LenSlots[len];
          m_MainCoder.CodeOneValue(&m_ReverseOutStream, kMatchNumber + lenSlot);
          m_OutStream.WriteBits(len - m_LenStart[lenSlot], m_LenDirectBits[lenSlot]);
          UInt32 dist = m_Values[i].Pos;
          UInt32 posSlot = GetPosSlot(dist);
          m_DistCoder.CodeOneValue(&m_ReverseOutStream, posSlot);
          m_OutStream.WriteBits(dist - kDistStart[posSlot], kDistDirectBits[posSlot]);
        }
      }
      m_MainCoder.CodeOneValue(&m_ReverseOutStream, kReadTableNumber);
    }
  }
  m_MainCoder.StartNewBlock();
  m_DistCoder.StartNewBlock();
  m_ValueIndex = 0;
  UInt32 i;
  for(i = 0; i < 256; i++)
    if(m_LastLevels[i] != 0)
      m_LiteralPrices[i] = m_LastLevels[i];
    else
      m_LiteralPrices[i] = kNoLiteralDummy;

  // -------------- Normal match -----------------------------
  
  for(i = 0; i < m_NumLenCombinations; i++)
  {
    UInt32 slot = g_LenSlots[i];
    Byte dummy = m_LastLevels[kMatchNumber + slot];
    if (dummy != 0)
      m_LenPrices[i] = dummy;
    else
      m_LenPrices[i] = kNoLenDummy;
    m_LenPrices[i] += m_LenDirectBits[slot];
  }
  for(i = 0; i < kDistTableSize64; i++)
  {
    Byte dummy = m_LastLevels[kDistTableStart + i];
    if (dummy != 0)
      m_PosPrices[i] = dummy;
    else
      m_PosPrices[i] = kNoPosDummy;
    m_PosPrices[i] += kDistDirectBits[i];
  }
}

void CCoder::CodeLevelTable(Byte *newLevels, int numLevels, bool codeMode)
{
  int prevLen = 0xFF;        // last emitted length
  int nextLen = newLevels[0]; // length of next code
  int count = 0;             // repeat count of the current code
  int maxCount = 7;          // max repeat count
  int minCount = 4;          // min repeat count
  if (nextLen == 0) 
  {
    maxCount = 138;
    minCount = 3;
  }
  Byte oldValueInGuardElement = newLevels[numLevels]; // push guard value
  try
  {
    newLevels[numLevels] = 0xFF; // guard already set
    for (int n = 0; n < numLevels; n++) 
    {
      int curLen = nextLen; 
      nextLen = newLevels[n + 1];
      count++;
      if (count < maxCount && curLen == nextLen) 
        continue;
      else if (count < minCount) 
        for(int i = 0; i < count; i++) 
        {
          int codeLen = curLen;
          if (codeMode)
            m_LevelCoder.CodeOneValue(&m_ReverseOutStream, codeLen);
          else
            m_LevelCoder.AddSymbol(codeLen);
        }
        else if (curLen != 0) 
        {
          if (curLen != prevLen) 
          {
            int codeLen = curLen;
            if (codeMode)
              m_LevelCoder.CodeOneValue(&m_ReverseOutStream, codeLen);
            else
              m_LevelCoder.AddSymbol(codeLen);
            count--;
          }
          if (codeMode)
          {
            m_LevelCoder.CodeOneValue(&m_ReverseOutStream, kTableLevelRepNumber);
            m_OutStream.WriteBits(count - 3, 2);
          }
          else
            m_LevelCoder.AddSymbol(kTableLevelRepNumber);
        } 
        else if (count <= 10) 
        {
          if (codeMode)
          {
            m_LevelCoder.CodeOneValue(&m_ReverseOutStream, kTableLevel0Number);
            m_OutStream.WriteBits(count - 3, 3);
          }
          else
            m_LevelCoder.AddSymbol(kTableLevel0Number);
        }
        else 
        {
          if (codeMode)
          {
            m_LevelCoder.CodeOneValue(&m_ReverseOutStream, kTableLevel0Number2);
            m_OutStream.WriteBits(count - 11, 7);
          }
          else
            m_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;
        }
    }
  }
  catch(...)
  {
    newLevels[numLevels] = oldValueInGuardElement; // old guard 
    throw;
  }
  newLevels[numLevels] = oldValueInGuardElement; // old guard 
}

int CCoder::WriteTables(bool writeMode, bool finalBlock)
{
  Byte newLevels[kMaxTableSize64 + 1]; // (+ 1) for guard 

  m_MainCoder.BuildTree(&newLevels[0]);
  m_DistCoder.BuildTree(&newLevels[kDistTableStart]);

  
  memset(m_LastLevels, 0, kMaxTableSize64);

  if (writeMode)
  {
    if(finalBlock)
      m_OutStream.WriteBits(NFinalBlockField::kFinalBlock, kFinalBlockFieldSize);
    else
      m_OutStream.WriteBits(NFinalBlockField::kNotFinalBlock, kFinalBlockFieldSize);
    
    m_LevelCoder.StartNewBlock();
    
    int numLitLenLevels = kMainTableSize;
    while(numLitLenLevels > kDeflateNumberOfLitLenCodesMin && newLevels[numLitLenLevels - 1] == 0)
      numLitLenLevels--;
    
    int numDistLevels = _deflate64Mode ? kDistTableSize64 : kDistTableSize32;
    while(numDistLevels > kDeflateNumberOfDistanceCodesMin && 
      newLevels[kDistTableStart + numDistLevels - 1] == 0)
      numDistLevels--;
    
    
    /////////////////////////
    // First Pass

    CodeLevelTable(newLevels, numLitLenLevels, false);
    CodeLevelTable(&newLevels[kDistTableStart], numDistLevels, false);

    memcpy(m_LastLevels, newLevels, kMaxTableSize64);
    

    Byte levelLevels[kLevelTableSize];
    m_LevelCoder.BuildTree(levelLevels);
    
    Byte levelLevelsStream[kLevelTableSize];
    int numLevelCodes = kDeflateNumberOfLevelCodesMin;
    int i;
    for (i = 0; i < kLevelTableSize; i++)
    {
      int streamPos = kCodeLengthAlphabetOrder[i];
      Byte level = levelLevels[streamPos]; 
      if (level > 0 && i >= numLevelCodes)
        numLevelCodes = i + 1;
      levelLevelsStream[i] = level;
    }
    
    UInt32 numLZHuffmanBits = m_MainCoder.GetBlockBitLength();
    numLZHuffmanBits += m_DistCoder.GetBlockBitLength();
    numLZHuffmanBits += m_LevelCoder.GetBlockBitLength();
    numLZHuffmanBits += kDeflateNumberOfLengthCodesFieldSize +
      kDeflateNumberOfDistanceCodesFieldSize +
      kDeflateNumberOfLevelCodesFieldSize;
    numLZHuffmanBits += numLevelCodes * kDeflateLevelCodeFieldSize;

    UInt32 nextBitPosition = 
        (m_OutStream.GetBitPosition() + kBlockTypeFieldSize) % 8;
    UInt32 numBitsForAlign = nextBitPosition > 0 ? (8 - nextBitPosition): 0;

    UInt32 numStoreBits = numBitsForAlign + (2 * 2) * 8;
    numStoreBits += m_CurrentBlockUncompressedSize * 8;
    if(numStoreBits < numLZHuffmanBits)
    {
      m_OutStream.WriteBits(NBlockType::kStored, kBlockTypeFieldSize); // test it
      m_OutStream.WriteBits(0, numBitsForAlign); // test it
      UInt16 currentBlockUncompressedSize = UInt16(m_CurrentBlockUncompressedSize);
      UInt16 currentBlockUncompressedSizeNot = ~currentBlockUncompressedSize;
      m_OutStream.WriteBits(currentBlockUncompressedSize, kDeflateStoredBlockLengthFieldSizeSize);
      m_OutStream.WriteBits(currentBlockUncompressedSizeNot, kDeflateStoredBlockLengthFieldSizeSize);
      return NBlockType::kStored;
    }
    else
    {
      m_OutStream.WriteBits(NBlockType::kDynamicHuffman, kBlockTypeFieldSize);
      m_OutStream.WriteBits(numLitLenLevels - kDeflateNumberOfLitLenCodesMin, kDeflateNumberOfLengthCodesFieldSize);
      m_OutStream.WriteBits(numDistLevels - kDeflateNumberOfDistanceCodesMin, 
        kDeflateNumberOfDistanceCodesFieldSize);
      m_OutStream.WriteBits(numLevelCodes - kDeflateNumberOfLevelCodesMin, 
        kDeflateNumberOfLevelCodesFieldSize);
      
      for (i = 0; i < numLevelCodes; i++)
        m_OutStream.WriteBits(levelLevelsStream[i], kDeflateLevelCodeFieldSize);
      
      /////////////////////////
      // Second Pass

      CodeLevelTable(newLevels, numLitLenLevels, true);
      CodeLevelTable(&newLevels[kDistTableStart], numDistLevels, true);
      return NBlockType::kDynamicHuffman;
    }
  }
  else
    memcpy(m_LastLevels, newLevels, kMaxTableSize64);
  return -1;
}

HRESULT CCoder::CodeReal(ISequentialInStream *inStream,
    ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize,
    ICompressProgressInfo *progress)
{
  if (!m_Created)
  {
    RINOK(Create());

    if (!m_MainCoder.Create(kMainTableSize, _deflate64Mode ? kLenDirectBits64 : kLenDirectBits32, 
        kMatchNumber, kMaxCodeBitLength))
      return E_OUTOFMEMORY;
    if (!m_DistCoder.Create(_deflate64Mode ? kDistTableSize64 : kDistTableSize32, 
        kDistDirectBits, 0, kMaxCodeBitLength))
      return E_OUTOFMEMORY;
    if (!m_LevelCoder.Create(kLevelTableSize, kLevelDirectBits, 0, kMaxLevelBitLength))
      return E_OUTOFMEMORY;
    m_Created = true;
  }

  UInt64 nowPos = 0;
  m_FinderPos = 0;

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

  CCoderReleaser coderReleaser(this);
  InitStructures();

  while(true)
  {
    int currentPassIndex = 0;
    bool noMoreBytes;
    while (true)
    {
      while(true)
      {
        noMoreBytes = (m_AdditionalOffset == 0 && m_MatchFinder->GetNumAvailableBytes() == 0);
  
        if (((m_CurrentBlockUncompressedSize >= kBlockUncompressedSizeThreshold || 
                 m_ValueIndex >= kValueBlockSize) && 
              (m_OptimumEndIndex == m_OptimumCurrentIndex)) 
            || noMoreBytes)
          break;
        UInt32 pos;
        UInt32 len = GetOptimal(pos);
        if (len >= kMatchMinLen)
        {
          UInt32 newLen = len - kMatchMinLen;
          m_Values[m_ValueIndex].Flag = kFlagLenPos;
          m_Values[m_ValueIndex].Len = Byte(newLen);
          UInt32 lenSlot = g_LenSlots[newLen];
          m_MainCoder.AddSymbol(kMatchNumber + lenSlot);
          m_Values[m_ValueIndex].Pos = UInt16(pos);
          UInt32 posSlot = GetPosSlot(pos);
          m_DistCoder.AddSymbol(posSlot);
        }
        else if (len == 1)  
        {
          Byte b = m_MatchFinder->GetIndexByte(0 - m_AdditionalOffset);
          len = 1;
          m_MainCoder.AddSymbol(b);
          m_Values[m_ValueIndex].Flag = kFlagImm;
          m_Values[m_ValueIndex].Imm = b;
        }
        else
          throw 12112342;
        m_ValueIndex++;
        m_AdditionalOffset -= len;
        nowPos += len;
        m_CurrentBlockUncompressedSize += len;
        
      }
      currentPassIndex++;
      bool writeMode = (currentPassIndex == m_NumPasses);
      WriteBlockData(writeMode, noMoreBytes);
      if (writeMode)
        break;
      nowPos = m_BlockStartPostion;
      m_AdditionalOffset = UInt32(m_FinderPos - m_BlockStartPostion);
      m_CurrentBlockUncompressedSize = 0;
    }
    m_BlockStartPostion += m_CurrentBlockUncompressedSize;
    m_CurrentBlockUncompressedSize = 0;
    if (progress != NULL)
    {
      UInt64 packSize = m_OutStream.GetProcessedSize();
      RINOK(progress->SetRatioInfo(&nowPos, &packSize));
    }
    if (noMoreBytes)
      break;
  }
  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.m_Result;   }
  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); }

}}}