bzip2encoder.cpp

seven zip源代码

// BZip2Encoder.cpp

#include "StdAfx.h"

extern "C" 
{ 
#include "../../../../C/Alloc.h"
}

#include "BZip2Encoder.h"

#include "../BWT/BlockSort.h"
#include "../BWT/Mtf8.h"
#include "BZip2CRC.h"

extern "C"
{
  #include "../../../../C/Compress/Huffman/HuffmanEncode.h"
}

namespace NCompress {
namespace NBZip2 {

const int kMaxHuffmanLenForEncoding = 16; // it must be < kMaxHuffmanLen = 20

static const UInt32 kBufferSize = (1 << 17);
static const int kNumHuffPasses = 4;

bool CThreadInfo::Alloc()
{
  if (m_BlockSorterIndex == 0)
  {
    m_BlockSorterIndex = (UInt32 *)::BigAlloc(BLOCK_SORT_BUF_SIZE(kBlockSizeMax) * sizeof(UInt32));
    if (m_BlockSorterIndex == 0)
      return false;
  }

  if (m_Block == 0)
  {
    m_Block = (Byte *)::MidAlloc(kBlockSizeMax * 5 + kBlockSizeMax / 10 + (20 << 10));
    if (m_Block == 0)
      return false;
    m_MtfArray = m_Block + kBlockSizeMax;
    m_TempArray = m_MtfArray + kBlockSizeMax * 2 + 2;
  }
  return true;
}

void CThreadInfo::Free()
{
  ::BigFree(m_BlockSorterIndex);
  m_BlockSorterIndex = 0;
  ::MidFree(m_Block);
  m_Block = 0;
}

#ifdef COMPRESS_BZIP2_MT

static THREAD_FUNC_DECL MFThread(void *threadCoderInfo)
{
  return ((CThreadInfo *)threadCoderInfo)->ThreadFunc();
}

HRes CThreadInfo::Create()
{
  RINOK(StreamWasFinishedEvent.Create());
  RINOK(WaitingWasStartedEvent.Create());
  RINOK(CanWriteEvent.Create());
  return Thread.Create(MFThread, this);
}

void CThreadInfo::FinishStream(bool needLeave)
{
  Encoder->StreamWasFinished = true;
  StreamWasFinishedEvent.Set();
  if (needLeave)
    Encoder->CS.Leave();
  Encoder->CanStartWaitingEvent.Lock();
  WaitingWasStartedEvent.Set();
}

DWORD CThreadInfo::ThreadFunc()
{
  for (;;)
  {
    Encoder->CanProcessEvent.Lock();
    Encoder->CS.Enter();
    if (Encoder->CloseThreads)
    {
      Encoder->CS.Leave();
      return 0;
    }
    if (Encoder->StreamWasFinished)
    {
      FinishStream(true);
      continue;
    }
    HRESULT res = S_OK;
    bool needLeave = true;
    try 
    {
      UInt32 blockSize = Encoder->ReadRleBlock(m_Block);
      m_PackSize = Encoder->m_InStream.GetProcessedSize();
      m_BlockIndex = Encoder->NextBlockIndex;
      if (++Encoder->NextBlockIndex == Encoder->NumThreads)
        Encoder->NextBlockIndex = 0;
      if (blockSize == 0)
      {
        FinishStream(true);
        continue;
      }
      Encoder->CS.Leave();
      needLeave = false;
      res = EncodeBlock3(blockSize);
    }
    catch(const CInBufferException &e)  { res = e.ErrorCode; }
    catch(const COutBufferException &e) { res = e.ErrorCode; }
    catch(...) { res = E_FAIL; }
    if (res != S_OK)
    {
      Encoder->Result = res;
      FinishStream(needLeave);
      continue;
    }
  }
}

#endif

CEncoder::CEncoder():
  NumPasses(1), 
  m_OptimizeNumTables(false),
  m_BlockSizeMult(kBlockSizeMultMax)
{
  #ifdef COMPRESS_BZIP2_MT
  ThreadsInfo = 0;
  m_NumThreadsPrev = 0;
  NumThreads = 1;
  #endif
}

#ifdef COMPRESS_BZIP2_MT
CEncoder::~CEncoder()
{
  Free();
}

HRes CEncoder::Create()
{
  RINOK(CanProcessEvent.CreateIfNotCreated());
  RINOK(CanStartWaitingEvent.CreateIfNotCreated());
  if (ThreadsInfo != 0 && m_NumThreadsPrev == NumThreads)
    return S_OK;
  try 
  { 
    Free();
    MtMode = (NumThreads > 1);
    m_NumThreadsPrev = NumThreads;
    ThreadsInfo = new CThreadInfo[NumThreads];
    if (ThreadsInfo == 0)
      return E_OUTOFMEMORY;
  }
  catch(...) { return E_OUTOFMEMORY; }
  for (UInt32 t = 0; t < NumThreads; t++)
  {
    CThreadInfo &ti = ThreadsInfo[t];
    ti.Encoder = this;
    if (MtMode)
    {
      HRes res = ti.Create();
      if (res != S_OK)
      {
        NumThreads = t;
        Free();
        return res; 
      }
    }
  }
  return S_OK;
}

void CEncoder::Free()
{
  if (!ThreadsInfo)
    return;
  CloseThreads = true;
  CanProcessEvent.Set();
  for (UInt32 t = 0; t < NumThreads; t++)
  {
    CThreadInfo &ti = ThreadsInfo[t];
    if (MtMode)
      ti.Thread.Wait();
    ti.Free();
  }
  delete []ThreadsInfo;
  ThreadsInfo = 0;
}
#endif

UInt32 CEncoder::ReadRleBlock(Byte *buffer)
{
  UInt32 i = 0;
  Byte prevByte;
  if (m_InStream.ReadByte(prevByte))
  {
    UInt32 blockSize = m_BlockSizeMult * kBlockSizeStep - 1;
    int numReps = 1;
    buffer[i++] = prevByte;
    while (i < blockSize) // "- 1" to support RLE
    {
      Byte b;
      if (!m_InStream.ReadByte(b))
        break;
      if (b != prevByte)
      {
        if (numReps >= kRleModeRepSize)
          buffer[i++] = (Byte)(numReps - kRleModeRepSize);
        buffer[i++] = b;
        numReps = 1;
        prevByte = b;
        continue;
      }
      numReps++;
      if (numReps <= kRleModeRepSize)
        buffer[i++] = b;
      else if (numReps == kRleModeRepSize + 255)
      {
        buffer[i++] = (Byte)(numReps - kRleModeRepSize);
        numReps = 0;
      }
    }
    // it's to support original BZip2 decoder
    if (numReps >= kRleModeRepSize)
      buffer[i++] = (Byte)(numReps - kRleModeRepSize);
  }
  return i;
}

void CThreadInfo::WriteBits2(UInt32 value, UInt32 numBits)
  { m_OutStreamCurrent->WriteBits(value, numBits); }
void CThreadInfo::WriteByte2(Byte b) { WriteBits2(b , 8); }
void CThreadInfo::WriteBit2(bool v) { WriteBits2((v ? 1 : 0), 1); }
void CThreadInfo::WriteCRC2(UInt32 v) 
{ 
  for (int i = 0; i < 4; i++)
    WriteByte2(((Byte)(v >> (24 - i * 8))));
}

void CEncoder::WriteBits(UInt32 value, UInt32 numBits)
  { m_OutStream.WriteBits(value, numBits); }
void CEncoder::WriteByte(Byte b) { WriteBits(b , 8); }
void CEncoder::WriteBit(bool v) { WriteBits((v ? 1 : 0), 1); }
void CEncoder::WriteCRC(UInt32 v) 
{ 
  for (int i = 0; i < 4; i++)
    WriteByte(((Byte)(v >> (24 - i * 8))));
}


// blockSize > 0
void CThreadInfo::EncodeBlock(const Byte *block, UInt32 blockSize)
{
  WriteBit2(false); // Randomised = false
  
  {
    UInt32 origPtr = BlockSort(m_BlockSorterIndex, block, blockSize);
    // if (m_BlockSorterIndex[origPtr] != 0) throw 1;
    m_BlockSorterIndex[origPtr] = blockSize;
    WriteBits2(origPtr, kNumOrigBits);
  }

  CMtf8Encoder mtf;
  int numInUse = 0;
  {
    bool inUse[256];
    bool inUse16[16];
    UInt32 i;
    for (i = 0; i < 256; i++) 
      inUse[i] = false;
    for (i = 0; i < 16; i++) 
      inUse16[i] = false;
    for (i = 0; i < blockSize; i++)
      inUse[block[i]] = true;
    for (i = 0; i < 256; i++) 
      if (inUse[i])
      {
        inUse16[i >> 4] = true;
        mtf.Buffer[numInUse++] = (Byte)i;
      }
    for (i = 0; i < 16; i++) 
      WriteBit2(inUse16[i]);
    for (i = 0; i < 256; i++) 
      if (inUse16[i >> 4])
        WriteBit2(inUse[i]);
  }
  int alphaSize = numInUse + 2;

  Byte *mtfs = m_MtfArray;
  UInt32 mtfArraySize = 0;
  UInt32 symbolCounts[kMaxAlphaSize];
  {
    for (int i = 0; i < kMaxAlphaSize; i++)
      symbolCounts[i] = 0;
  }

  {
    UInt32 rleSize = 0;
    UInt32 i = 0;
    const UInt32 *bsIndex = m_BlockSorterIndex;
    block--;
    do 
    {
      int pos = mtf.FindAndMove(block[bsIndex[i]]);
      if (pos == 0)
        rleSize++;
      else
      {
        while (rleSize != 0)
        {
          rleSize--;
          mtfs[mtfArraySize++] = (Byte)(rleSize & 1);
          symbolCounts[rleSize & 1]++;
          rleSize >>= 1;
        }
        if (pos >= 0xFE)
        {
          mtfs[mtfArraySize++] = 0xFF;
          mtfs[mtfArraySize++] = (Byte)(pos - 0xFE);
        }
        else
          mtfs[mtfArraySize++] = (Byte)(pos + 1);
        symbolCounts[pos + 1]++;
      }
    }
    while (++i < blockSize);

    while (rleSize != 0)
    {
      rleSize--;
      mtfs[mtfArraySize++] = (Byte)(rleSize & 1);
      symbolCounts[rleSize & 1]++;
      rleSize >>= 1;
    }

    if (alphaSize < 256)
      mtfs[mtfArraySize++] = (Byte)(alphaSize - 1);
    else
    {
      mtfs[mtfArraySize++] = 0xFF;
      mtfs[mtfArraySize++] = (Byte)(alphaSize - 256);
    }
    symbolCounts[alphaSize - 1]++;
  }

  UInt32 numSymbols = 0;
  {
    for (int i = 0; i < kMaxAlphaSize; i++)
      numSymbols += symbolCounts[i];
  }

  int bestNumTables = kNumTablesMin;
  UInt32 bestPrice = 0xFFFFFFFF;
  UInt32 startPos = m_OutStreamCurrent->GetPos();
  Byte startCurByte = m_OutStreamCurrent->GetCurByte();
  for (int nt = kNumTablesMin; nt <= kNumTablesMax + 1; nt++)
  {
    int numTables;

    if(m_OptimizeNumTables)
    {
      m_OutStreamCurrent->SetPos(startPos);
      m_OutStreamCurrent->SetCurState((startPos & 7), startCurByte);
      if (nt <= kNumTablesMax)
        numTables = nt;
      else
        numTables = bestNumTables;
    }
    else
    {
      if (numSymbols < 200)  numTables = 2; 
      else if (numSymbols < 600) numTables = 3; 
      else if (numSymbols < 1200) numTables = 4; 
      else if (numSymbols < 2400) numTables = 5; 
      else numTables = 6;
    }

    WriteBits2(numTables, kNumTablesBits);
    
    UInt32 numSelectors = (numSymbols + kGroupSize - 1) / kGroupSize;
    WriteBits2(numSelectors, kNumSelectorsBits);
    
    {
      UInt32 remFreq = numSymbols;
      int gs = 0;
      int t = numTables;
      do
      {
        UInt32 tFreq = remFreq / t;
        int ge = gs;
        UInt32 aFreq = 0;
        while (aFreq < tFreq) //  && ge < alphaSize) 
          aFreq += symbolCounts[ge++];
        
        if (ge - 1 > gs && t != numTables && t != 1 && (((numTables - t) & 1) == 1)) 
          aFreq -= symbolCounts[--ge];
        
        Byte *lens = Lens[t - 1];
        int i = 0;
        do
          lens[i] = (i >= gs && i < ge) ? 0 : 1;
        while (++i < alphaSize);
        gs = ge;
        remFreq -= aFreq;
      }
      while(--t != 0);
    }
    
    
    for (int pass = 0; pass < kNumHuffPasses; pass++)
    {
      {
        int t = 0;
        do
          memset(Freqs[t], 0, sizeof(Freqs[t]));
        while(++t < numTables);
      }
      
      {
        UInt32 mtfPos = 0;
        UInt32 g = 0;
        do 
        {
          UInt32 symbols[kGroupSize];
          int i = 0;
          do
          {
            UInt32 symbol = mtfs[mtfPos++];
            if (symbol >= 0xFF)
              symbol += mtfs[mtfPos++];
            symbols[i] = symbol;
          }
          while (++i < kGroupSize && mtfPos < mtfArraySize);
          
          UInt32 bestPrice = 0xFFFFFFFF;
          int t = 0;
          do
          {
            const Byte *lens = Lens[t];
            UInt32 price = 0;
            int j = 0;
            do