7zin.cpp

7z一个高压缩比的压缩程序源代码,重要的是里面的算法值得学习

// 7zIn.cpp

#include "StdAfx.h"

extern "C"
{
  #include "../../../../C/7zCrc.h"
  #include "../../../../C/CpuArch.h"
}

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

#include "7zDecode.h"
#include "7zIn.h"

#define Get16(p) GetUi16(p)
#define Get32(p) GetUi32(p)
#define Get64(p) GetUi64(p)

// define FORMAT_7Z_RECOVERY if you want to recover multivolume archives with empty StartHeader
#ifndef _SFX
#define FORMAT_7Z_RECOVERY
#endif

namespace NArchive {
namespace N7z {

static void BoolVector_Fill_False(CBoolVector &v, int size)
{
  v.Clear();
  v.Reserve(size);
  for (int i = 0; i < size; i++)
    v.Add(false);
}

static bool BoolVector_GetAndSet(CBoolVector &v, UInt32 index)
{
  if (index >= (UInt32)v.Size())
    return true;
  bool res = v[index];
  v[index] = true;
  return res;
}

bool CFolder::CheckStructure() const
{
  const int kNumCodersMax = sizeof(UInt32) * 8; // don't change it
  const int kMaskSize = sizeof(UInt32) * 8; // it must be >= kNumCodersMax
  const int kNumBindsMax = 32;

  if (Coders.Size() > kNumCodersMax || BindPairs.Size() > kNumBindsMax)
    return false;

  {
    CBoolVector v;
    BoolVector_Fill_False(v, BindPairs.Size() + PackStreams.Size());
    
    int i;
    for (i = 0; i < BindPairs.Size(); i++)
      if (BoolVector_GetAndSet(v, BindPairs[i].InIndex))
        return false;
    for (i = 0; i < PackStreams.Size(); i++)
      if (BoolVector_GetAndSet(v, PackStreams[i]))
        return false;
    
    BoolVector_Fill_False(v, UnpackSizes.Size());
    for (i = 0; i < BindPairs.Size(); i++)
      if (BoolVector_GetAndSet(v, BindPairs[i].OutIndex))
        return false;
  }
  
  UInt32 mask[kMaskSize];
  int i;
  for (i = 0; i < kMaskSize; i++)
    mask[i] = 0;

  {
    CIntVector inStreamToCoder, outStreamToCoder;
    for (i = 0; i < Coders.Size(); i++)
    {
      CNum j;
      const CCoderInfo &coder = Coders[i];
      for (j = 0; j < coder.NumInStreams; j++)
        inStreamToCoder.Add(i);
      for (j = 0; j < coder.NumOutStreams; j++)
        outStreamToCoder.Add(i);
    }
    
    for (i = 0; i < BindPairs.Size(); i++)
    {
      const CBindPair &bp = BindPairs[i];
      mask[inStreamToCoder[bp.InIndex]] |= (1 << outStreamToCoder[bp.OutIndex]);
    }
  }
  
  for (i = 0; i < kMaskSize; i++)
    for (int j = 0; j < kMaskSize; j++)
      if (((1 << j) & mask[i]) != 0)
        mask[i] |= mask[j];

  for (i = 0; i < kMaskSize; i++)
    if (((1 << i) & mask[i]) != 0)
      return false;

  return true;
}

class CInArchiveException {};

static void ThrowException() { throw CInArchiveException(); }
static inline void ThrowEndOfData()   { ThrowException(); }
static inline void ThrowUnsupported() { ThrowException(); }
static inline void ThrowIncorrect()   { ThrowException(); }
static inline void ThrowUnsupportedVersion() { ThrowException(); }

/*
class CInArchiveException
{
public:
  enum CCauseType
  {
    kUnsupportedVersion = 0,
    kUnsupported,
    kIncorrect,
    kEndOfData,
  } Cause;
  CInArchiveException(CCauseType cause): Cause(cause) {};
};

static void ThrowException(CInArchiveException::CCauseType c) { throw CInArchiveException(c); }
static void ThrowEndOfData()   { ThrowException(CInArchiveException::kEndOfData); }
static void ThrowUnsupported() { ThrowException(CInArchiveException::kUnsupported); }
static void ThrowIncorrect()   { ThrowException(CInArchiveException::kIncorrect); }
static void ThrowUnsupportedVersion() { ThrowException(CInArchiveException::kUnsupportedVersion); }
*/

class CStreamSwitch
{
  CInArchive *_archive;
  bool _needRemove;
public:
  CStreamSwitch(): _needRemove(false) {}
  ~CStreamSwitch() { Remove(); }
  void Remove();
  void Set(CInArchive *archive, const Byte *data, size_t size);
  void Set(CInArchive *archive, const CByteBuffer &byteBuffer);
  void Set(CInArchive *archive, const CObjectVector<CByteBuffer> *dataVector);
};

void CStreamSwitch::Remove()
{
  if (_needRemove)
  {
    _archive->DeleteByteStream();
    _needRemove = false;
  }
}

void CStreamSwitch::Set(CInArchive *archive, const Byte *data, size_t size)
{
  Remove();
  _archive = archive;
  _archive->AddByteStream(data, size);
  _needRemove = true;
}

void CStreamSwitch::Set(CInArchive *archive, const CByteBuffer &byteBuffer)
{
  Set(archive, byteBuffer, byteBuffer.GetCapacity());
}

void CStreamSwitch::Set(CInArchive *archive, const CObjectVector<CByteBuffer> *dataVector)
{
  Remove();
  Byte external = archive->ReadByte();
  if (external != 0)
  {
    int dataIndex = (int)archive->ReadNum();
    if (dataIndex < 0 || dataIndex >= dataVector->Size())
      ThrowIncorrect();
    Set(archive, (*dataVector)[dataIndex]);
  }
}

Byte CInByte2::ReadByte()
{
  if (_pos >= _size)
    ThrowEndOfData();
  return _buffer[_pos++];
}

void CInByte2::ReadBytes(Byte *data, size_t size)
{
  if (size > _size - _pos)
    ThrowEndOfData();
  for (size_t i = 0; i < size; i++)
    data[i] = _buffer[_pos++];
}

void CInByte2::SkeepData(UInt64 size)
{
  if (size > _size - _pos)
    ThrowEndOfData();
  _pos += (size_t)size;
}

void CInByte2::SkeepData()
{
  SkeepData(ReadNumber());
}

UInt64 CInByte2::ReadNumber()
{
  if (_pos >= _size)
    ThrowEndOfData();
  Byte firstByte = _buffer[_pos++];
  Byte mask = 0x80;
  UInt64 value = 0;
  for (int i = 0; i < 8; i++)
  {
    if ((firstByte & mask) == 0)
    {
      UInt64 highPart = firstByte & (mask - 1);
      value += (highPart << (i * 8));
      return value;
    }
    if (_pos >= _size)
      ThrowEndOfData();
    value |= ((UInt64)_buffer[_pos++] << (8 * i));
    mask >>= 1;
  }
  return value;
}

CNum CInByte2::ReadNum()
{
  UInt64 value = ReadNumber();
  if (value > kNumMax)
    ThrowUnsupported();
  return (CNum)value;
}

UInt32 CInByte2::ReadUInt32()
{
  if (_pos + 4 > _size)
    ThrowEndOfData();
  UInt32 res = Get32(_buffer + _pos);
  _pos += 4;
  return res;
}

UInt64 CInByte2::ReadUInt64()
{
  if (_pos + 8 > _size)
    ThrowEndOfData();
  UInt64 res = Get64(_buffer + _pos);
  _pos += 8;
  return res;
}

void CInByte2::ReadString(UString &s)
{
  const Byte *buf = _buffer + _pos;
  size_t rem = (_size - _pos) / 2 * 2;
  {
    size_t i;
    for (i = 0; i < rem; i += 2)
      if (buf[i] == 0 && buf[i + 1] == 0)
        break;
    if (i == rem)
      ThrowEndOfData();
    rem = i;
  }
  int len = (int)(rem / 2);
  if (len < 0 || (size_t)len * 2 != rem)
    ThrowUnsupported();
  wchar_t *p = s.GetBuffer(len);
  int i;
  for (i = 0; i < len; i++, buf += 2)
    p[i] = (wchar_t)Get16(buf);
  s.ReleaseBuffer(len);
  _pos += rem + 2;
}

static inline bool TestSignatureCandidate(const Byte *p)
{
  for (int i = 0; i < kSignatureSize; i++)
    if (p[i] != kSignature[i])
      return false;
  return (p[0x1A] == 0 && p[0x1B] == 0);
}

HRESULT CInArchive::FindAndReadSignature(IInStream *stream, const UInt64 *searchHeaderSizeLimit)
{
  RINOK(ReadStream_FALSE(stream, _header, kHeaderSize));

  if (TestSignatureCandidate(_header))
    return S_OK;

  CByteBuffer byteBuffer;
  const UInt32 kBufferSize = (1 << 16);
  byteBuffer.SetCapacity(kBufferSize);
  Byte *buffer = byteBuffer;
  UInt32 numPrevBytes = kHeaderSize - 1;
  memcpy(buffer, _header + 1, numPrevBytes);
  UInt64 curTestPos = _arhiveBeginStreamPosition + 1;
  for (;;)
  {
    if (searchHeaderSizeLimit != NULL)
      if (curTestPos - _arhiveBeginStreamPosition > *searchHeaderSizeLimit)
        break;
    do
    {
      UInt32 numReadBytes = kBufferSize - numPrevBytes;
      UInt32 processedSize;
      RINOK(stream->Read(buffer + numPrevBytes, numReadBytes, &processedSize));
      numPrevBytes += processedSize;
      if (processedSize == 0)
        return S_FALSE;
    }
    while (numPrevBytes < kHeaderSize);
    UInt32 numTests = numPrevBytes - kHeaderSize + 1;
    for (UInt32 pos = 0; pos < numTests; pos++)
    {
      for (; buffer[pos] != '7' && pos < numTests; pos++);
      if (pos == numTests)
        break;
      if (TestSignatureCandidate(buffer + pos))
      {
        memcpy(_header, buffer + pos, kHeaderSize);
        curTestPos += pos;
        _arhiveBeginStreamPosition = curTestPos;
        return stream->Seek(curTestPos + kHeaderSize, STREAM_SEEK_SET, NULL);
      }
    }
    curTestPos += numTests;
    numPrevBytes -= numTests;
    memmove(buffer, buffer + numTests, numPrevBytes);
  }
  return S_FALSE;
}

// S_FALSE means that file is not archive
HRESULT CInArchive::Open(IInStream *stream, const UInt64 *searchHeaderSizeLimit)
{
  HeadersSize = 0;
  Close();
  RINOK(stream->Seek(0, STREAM_SEEK_CUR, &_arhiveBeginStreamPosition))
  RINOK(FindAndReadSignature(stream, searchHeaderSizeLimit));
  _stream = stream;
  return S_OK;
}
  
void CInArchive::Close()
{
  _stream.Release();
}

void CInArchive::ReadArchiveProperties(CInArchiveInfo & /* archiveInfo */)
{
  for (;;)
  {
    if (ReadID() == NID::kEnd)
      break;
    SkeepData();
  }
}

void CInArchive::GetNextFolderItem(CFolder &folder)
{
  CNum numCoders = ReadNum();

  folder.Coders.Clear();
  folder.Coders.Reserve((int)numCoders);
  CNum numInStreams = 0;
  CNum numOutStreams = 0;
  CNum i;
  for (i = 0; i < numCoders; i++)
  {
    folder.Coders.Add(CCoderInfo());
    CCoderInfo &coder = folder.Coders.Back();

    {
      Byte mainByte = ReadByte();
      int idSize = (mainByte & 0xF);
      Byte longID[15];
      ReadBytes(longID, idSize);
      if (idSize > 8)
        ThrowUnsupported();
      UInt64 id = 0;
      for (int j = 0; j < idSize; j++)
        id |= (UInt64)longID[idSize - 1 - j] << (8 * j);
      coder.MethodID = id;

      if ((mainByte & 0x10) != 0)
      {
        coder.NumInStreams = ReadNum();
        coder.NumOutStreams = ReadNum();
      }
      else
      {
        coder.NumInStreams = 1;
        coder.NumOutStreams = 1;
      }
      if ((mainByte & 0x20) != 0)
      {
        CNum propsSize = ReadNum();
        coder.Props.SetCapacity((size_t)propsSize);
        ReadBytes((Byte *)coder.Props, (size_t)propsSize);
      }
      if ((mainByte & 0x80) != 0)
        ThrowUnsupported();
    }
    numInStreams += coder.NumInStreams;
    numOutStreams += coder.NumOutStreams;
  }

  CNum numBindPairs = numOutStreams - 1;
  folder.BindPairs.Clear();
  folder.BindPairs.Reserve(numBindPairs);