rar3decoder.cpp

7-Zip 是一款号称有着现今最高压缩比的压缩软件

// Rar3Decoder.cpp
// According to unRAR license, this code may not be used to develop
// a program that creates RAR archives
 
#include "StdAfx.h"

#include "Rar3Decoder.h"
#include "../../Common/StreamUtils.h"

namespace NCompress {
namespace NRar3 {

static const UInt32 kNumAlignReps = 15;

static const UInt32 kSymbolReadTable = 256;
static const UInt32 kSymbolRep = 259;
static const UInt32 kSymbolLen2 = kSymbolRep + kNumReps;

static const Byte kLenStart[kLenTableSize]      = {0,1,2,3,4,5,6,7,8,10,12,14,16,20,24,28,32,40,48,56,64,80,96,112,128,160,192,224};
static const Byte kLenDirectBits[kLenTableSize] = {0,0,0,0,0,0,0,0,1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,  4,  5,  5,  5,  5};

static const Byte kDistDirectBits[kDistTableSize] =
  {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,
  16,16,16,16,16,16,16,16,16,16,16,16,16,16,
  18,18,18,18,18,18,18,18,18,18,18,18};

static const Byte kLevelDirectBits[kLevelTableSize] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};

static const Byte kLen2DistStarts[kNumLen2Symbols]={0,4,8,16,32,64,128,192};
static const Byte kLen2DistDirectBits[kNumLen2Symbols]={2,2,3, 4, 5, 6,  6,  6};

static const UInt32 kDistLimit3 = 0x2000 - 2;
static const UInt32 kDistLimit4 = 0x40000 - 2;

static const UInt32 kNormalMatchMinLen = 3;

static const UInt32 kVmDataSizeMax = 1 << 16;
static const UInt32 kVmCodeSizeMax = 1 << 16;

CDecoder::CDecoder():
  _window(0),
  _winPos(0),
  _wrPtr(0),
  _lzSize(0),
  _writtenFileSize(0),
  _vmData(0),
  _vmCode(0),
  m_IsSolid(false)
{
}

CDecoder::~CDecoder()
{
  InitFilters();
  ::MidFree(_vmData);
  ::MidFree(_window);
}

HRESULT CDecoder::WriteDataToStream(const Byte *data, UInt32 size)
{
  return WriteStream(_outStream, data, size);
}

HRESULT CDecoder::WriteData(const Byte *data, UInt32 size)
{
  HRESULT res = S_OK;
  if (_writtenFileSize < _unpackSize)
  {
    UInt32 curSize = size;
    UInt64 remain = _unpackSize - _writtenFileSize;
    if (remain < curSize)
      curSize = (UInt32)remain;
    res = WriteDataToStream(data, curSize);
  }
  _writtenFileSize += size;
  return res;
}

HRESULT CDecoder::WriteArea(UInt32 startPtr, UInt32 endPtr)
{
  if (startPtr <= endPtr)
    return WriteData(_window + startPtr, endPtr - startPtr);
  RINOK(WriteData(_window + startPtr, kWindowSize - startPtr));
  return WriteData(_window, endPtr);
}

void CDecoder::ExecuteFilter(int tempFilterIndex, NVm::CBlockRef &outBlockRef)
{
  CTempFilter *tempFilter = _tempFilters[tempFilterIndex];
  tempFilter->InitR[6] = (UInt32)_writtenFileSize;
  NVm::SetValue32(&tempFilter->GlobalData[0x24], (UInt32)_writtenFileSize);
  NVm::SetValue32(&tempFilter->GlobalData[0x28], (UInt32)(_writtenFileSize >> 32));
  CFilter *filter = _filters[tempFilter->FilterIndex];
  _vm.Execute(filter, tempFilter, outBlockRef, filter->GlobalData);
  delete tempFilter;
  _tempFilters[tempFilterIndex] = 0;
}

HRESULT CDecoder::WriteBuf()
{
  UInt32 writtenBorder = _wrPtr;
  UInt32 writeSize = (_winPos - writtenBorder) & kWindowMask;
  for (int i = 0; i < _tempFilters.Size(); i++)
  {
    CTempFilter *filter = _tempFilters[i];
    if (filter == NULL)
      continue;
    if (filter->NextWindow)
    {
      filter->NextWindow = false;
      continue;
    }
    UInt32 blockStart = filter->BlockStart;
    UInt32 blockSize = filter->BlockSize;
    if (((blockStart - writtenBorder) & kWindowMask) < writeSize)
    {
      if (writtenBorder != blockStart)
      {
        RINOK(WriteArea(writtenBorder, blockStart));
        writtenBorder = blockStart;
        writeSize = (_winPos - writtenBorder) & kWindowMask;
      }
      if (blockSize <= writeSize)
      {
        UInt32 blockEnd = (blockStart + blockSize) & kWindowMask;
        if (blockStart < blockEnd || blockEnd == 0)
          _vm.SetMemory(0, _window + blockStart, blockSize);
        else
        {
          UInt32 tailSize = kWindowSize - blockStart;
          _vm.SetMemory(0, _window + blockStart, tailSize);
          _vm.SetMemory(tailSize, _window, blockEnd);
        }
        NVm::CBlockRef outBlockRef;
        ExecuteFilter(i, outBlockRef);
        while (i + 1 < _tempFilters.Size())
        {
          CTempFilter *nextFilter = _tempFilters[i + 1];
          if (nextFilter == NULL || nextFilter->BlockStart != blockStart ||
              nextFilter->BlockSize != outBlockRef.Size || nextFilter->NextWindow)
            break;
          _vm.SetMemory(0, _vm.GetDataPointer(outBlockRef.Offset), outBlockRef.Size);
          ExecuteFilter(++i, outBlockRef);
        }
        WriteDataToStream(_vm.GetDataPointer(outBlockRef.Offset), outBlockRef.Size);
        _writtenFileSize += outBlockRef.Size;
        writtenBorder = blockEnd;
        writeSize = (_winPos - writtenBorder) & kWindowMask;
      }
      else
      {
        for (int j = i; j < _tempFilters.Size(); j++)
        {
          CTempFilter *filter = _tempFilters[j];
          if (filter != NULL && filter->NextWindow)
            filter->NextWindow = false;
        }
        _wrPtr = writtenBorder;
        return S_OK; // check it
      }
    }
  }
      
  _wrPtr = _winPos;
  return WriteArea(writtenBorder, _winPos);
}

void CDecoder::InitFilters()
{
  _lastFilter = 0;
  int i;
  for (i = 0; i < _tempFilters.Size(); i++)
    delete _tempFilters[i];
  _tempFilters.Clear();
  for (i = 0; i < _filters.Size(); i++)
    delete _filters[i];
  _filters.Clear();
}

bool CDecoder::AddVmCode(UInt32 firstByte, UInt32 codeSize)
{
  CMemBitDecoder inp;
  inp.Init(_vmData, codeSize);

  UInt32 filterIndex;
  if (firstByte & 0x80)
  {
    filterIndex = NVm::ReadEncodedUInt32(inp);
    if (filterIndex == 0)
      InitFilters();
    else
      filterIndex--;
  }
  else
    filterIndex = _lastFilter;
  if (filterIndex > (UInt32)_filters.Size())
    return false;
  _lastFilter = filterIndex;
  bool newFilter = (filterIndex == (UInt32)_filters.Size());

  CFilter *filter;
  if (newFilter)
  {
    // check if too many filters
    if (filterIndex > 1024)
      return false;
    filter = new CFilter;
    _filters.Add(filter);
  }
  else
  {
    filter = _filters[filterIndex];
    filter->ExecCount++;
  }

  int numEmptyItems = 0;
  int i;
  for (i = 0; i < _tempFilters.Size(); i++)
  {
    _tempFilters[i - numEmptyItems] = _tempFilters[i];
    if (_tempFilters[i] == NULL)
      numEmptyItems++;
    if (numEmptyItems > 0)
      _tempFilters[i] = NULL;
  }
  if (numEmptyItems == 0)
  {
    _tempFilters.Add(NULL);
    numEmptyItems = 1;
  }
  CTempFilter *tempFilter = new CTempFilter;
  _tempFilters[_tempFilters.Size() - numEmptyItems] = tempFilter;
  tempFilter->FilterIndex = filterIndex;
  tempFilter->ExecCount = filter->ExecCount;
 
  UInt32 blockStart = NVm::ReadEncodedUInt32(inp);
  if (firstByte & 0x40)
    blockStart += 258;
  tempFilter->BlockStart = (blockStart + _winPos) & kWindowMask;
  if (firstByte & 0x20)
    filter->BlockSize = NVm::ReadEncodedUInt32(inp);
  tempFilter->BlockSize = filter->BlockSize;
  tempFilter->NextWindow = _wrPtr != _winPos && ((_wrPtr - _winPos) & kWindowMask) <= blockStart;

  memset(tempFilter->InitR, 0, sizeof(tempFilter->InitR));
  tempFilter->InitR[3] = NVm::kGlobalOffset;
  tempFilter->InitR[4] = tempFilter->BlockSize;
  tempFilter->InitR[5] = tempFilter->ExecCount;
  if (firstByte & 0x10)
  {
    UInt32 initMask = inp.ReadBits(NVm::kNumGpRegs);
    for (int i = 0; i < NVm::kNumGpRegs; i++)
      if (initMask & (1 << i))
        tempFilter->InitR[i] = NVm::ReadEncodedUInt32(inp);
  }
  if (newFilter)
  {
    UInt32 vmCodeSize = NVm::ReadEncodedUInt32(inp);
    if (vmCodeSize >= kVmCodeSizeMax || vmCodeSize == 0)
      return false;
    for (UInt32 i = 0; i < vmCodeSize; i++)
      _vmCode[i] = (Byte)inp.ReadBits(8);
    _vm.PrepareProgram(_vmCode, vmCodeSize, filter);
  }

  tempFilter->AllocateEmptyFixedGlobal();

  Byte *globalData = &tempFilter->GlobalData[0];
  for (i = 0; i < NVm::kNumGpRegs; i++)
    NVm::SetValue32(&globalData[i * 4], tempFilter->InitR[i]);
  NVm::SetValue32(&globalData[NVm::NGlobalOffset::kBlockSize], tempFilter->BlockSize);
  NVm::SetValue32(&globalData[NVm::NGlobalOffset::kBlockPos], 0); // It was commented. why?
  NVm::SetValue32(&globalData[NVm::NGlobalOffset::kExecCount], tempFilter->ExecCount);

  if (firstByte & 8)
  {
    UInt32 dataSize = NVm::ReadEncodedUInt32(inp);
    if (dataSize > NVm::kGlobalSize - NVm::kFixedGlobalSize)
      return false;
    CRecordVector<Byte> &globalData = tempFilter->GlobalData;
    int requredSize = (int)(dataSize + NVm::kFixedGlobalSize);
    if (globalData.Size() < requredSize)
    {
      globalData.Reserve(requredSize);
      for (; globalData.Size() < requredSize; i++)
        globalData.Add(0);
    }
    for (UInt32 i = 0; i < dataSize; i++)
      globalData[NVm::kFixedGlobalSize + i] = (Byte)inp.ReadBits(8);
  }
  return true;
}

bool CDecoder::ReadVmCodeLZ()
{
  UInt32 firstByte = m_InBitStream.ReadBits(8);
  UInt32 length = (firstByte & 7) + 1;
  if (length == 7)
    length = m_InBitStream.ReadBits(8) + 7;
  else if (length == 8)
    length = m_InBitStream.ReadBits(16);
  if (length > kVmDataSizeMax)
    return false;
  for (UInt32 i = 0; i < length; i++)
    _vmData[i] = (Byte)m_InBitStream.ReadBits(8);
  return AddVmCode(firstByte, length);
}

bool CDecoder::ReadVmCodePPM()
{
  int firstByte = DecodePpmSymbol();
  if (firstByte == -1)
    return false;
  UInt32 length = (firstByte & 7) + 1;
  if (length == 7)
  {
    int b1 = DecodePpmSymbol();
    if (b1 == -1)
      return false;
    length = b1 + 7;
  }
  else if (length == 8)
  {
    int b1 = DecodePpmSymbol();
    if (b1 == -1)
      return false;
    int b2 = DecodePpmSymbol();
    if (b2 == -1)
      return false;
    length = b1 * 256 + b2;
  }
  if (length > kVmDataSizeMax)
    return false;
  for (UInt32 i = 0; i < length; i++)
  {
    int b = DecodePpmSymbol();
    if (b == -1)
      return false;
    _vmData[i] = (Byte)b;
  }
  return AddVmCode(firstByte, length);
}

#define RIF(x) { if (!(x)) return S_FALSE; }

UInt32 CDecoder::ReadBits(int numBits) { return m_InBitStream.ReadBits(numBits); }

/////////////////////////////////////////////////
// PPM

HRESULT CDecoder::InitPPM()
{
  Byte maxOrder = (Byte)ReadBits(7);

  bool reset = ((maxOrder & 0x20) != 0);
  int maxMB = 0;
  if (reset)
    maxMB = (Byte)ReadBits(8);
  else
  {
    if (_ppm.SubAllocator.GetSubAllocatorSize()== 0)
      return S_FALSE;
  }
  if (maxOrder & 0x40)
    PpmEscChar = (Byte)ReadBits(8);
  m_InBitStream.InitRangeCoder();
  /*
  if (m_InBitStream.m_BitPos != 0)
    return S_FALSE;
  */
  if (reset)
  {
    maxOrder = (maxOrder & 0x1F) + 1;
    if (maxOrder > 16)
      maxOrder = 16 + (maxOrder - 16) * 3;
    if (maxOrder == 1)
    {
      // SubAlloc.StopSubAllocator();
      _ppm.SubAllocator.StopSubAllocator();
      return S_FALSE;
    }
    // SubAlloc.StartSubAllocator(MaxMB+1);
    // StartModelRare(maxOrder);

    if (!_ppm.SubAllocator.StartSubAllocator((maxMB + 1) << 20))
      return E_OUTOFMEMORY;
    _ppm.MaxOrder = 0;
    _ppm.StartModelRare(maxOrder);

  }
  // return (minContext != NULL);

  return S_OK;
}

int CDecoder::DecodePpmSymbol() { return _ppm.DecodeSymbol(&m_InBitStream); }

HRESULT CDecoder::DecodePPM(Int32 num, bool &keepDecompressing)
{
  keepDecompressing = false;
  do
  {
    if (((_wrPtr - _winPos) & kWindowMask) < 260 && _wrPtr != _winPos)
    {
      RINOK(WriteBuf());
      if (_writtenFileSize > _unpackSize)
      {
        keepDecompressing = false;
        return S_OK;
      }
    }
    int c = DecodePpmSymbol();
    if (c == -1)
    {
      // Original code sets PPMError=true here and then it returns S_OK. Why ???
      // return S_OK;
      return S_FALSE;
    }