openarchive.cpp

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

// OpenArchive.cpp

#include "StdAfx.h"

#include "OpenArchive.h"

#include "Common/Wildcard.h"

#include "Windows/FileName.h"
#include "Windows/FileDir.h"
#include "Windows/Defs.h"
#include "Windows/PropVariant.h"

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

#include "Common/StringConvert.h"

#include "DefaultName.h"

using namespace NWindows;

HRESULT GetArchiveItemPath(IInArchive *archive, UInt32 index, UString &result)
{
  NCOM::CPropVariant prop;
  RINOK(archive->GetProperty(index, kpidPath, &prop));
  if(prop.vt == VT_BSTR)
    result = prop.bstrVal;
  else if (prop.vt == VT_EMPTY)
    result.Empty();
  else
    return E_FAIL;
  return S_OK;
}

HRESULT GetArchiveItemPath(IInArchive *archive, UInt32 index, const UString &defaultName, UString &result)
{
  RINOK(GetArchiveItemPath(archive, index, result));
  if (result.IsEmpty())
  {
    result = defaultName;
    NCOM::CPropVariant prop;
    RINOK(archive->GetProperty(index, kpidExtension, &prop));
    if (prop.vt == VT_BSTR)
    {
      result += L'.';
      result += prop.bstrVal;
    }
    else if (prop.vt != VT_EMPTY)
      return E_FAIL;
  }
  return S_OK;
}

HRESULT GetArchiveItemFileTime(IInArchive *archive, UInt32 index,
    const FILETIME &defaultFileTime, FILETIME &fileTime)
{
  NCOM::CPropVariant prop;
  RINOK(archive->GetProperty(index, kpidMTime, &prop));
  if (prop.vt == VT_FILETIME)
    fileTime = prop.filetime;
  else if (prop.vt == VT_EMPTY)
    fileTime = defaultFileTime;
  else
    return E_FAIL;
  return S_OK;
}

HRESULT IsArchiveItemProp(IInArchive *archive, UInt32 index, PROPID propID, bool &result)
{
  NCOM::CPropVariant prop;
  RINOK(archive->GetProperty(index, propID, &prop));
  if(prop.vt == VT_BOOL)
    result = VARIANT_BOOLToBool(prop.boolVal);
  else if (prop.vt == VT_EMPTY)
    result = false;
  else
    return E_FAIL;
  return S_OK;
}

HRESULT IsArchiveItemFolder(IInArchive *archive, UInt32 index, bool &result)
{
  return IsArchiveItemProp(archive, index, kpidIsDir, result);
}

HRESULT IsArchiveItemAnti(IInArchive *archive, UInt32 index, bool &result)
{
  return IsArchiveItemProp(archive, index, kpidIsAnti, result);
}

// Static-SFX (for Linux) can be big.
const UInt64 kMaxCheckStartPosition = 1 << 22;

HRESULT ReOpenArchive(IInArchive *archive, const UString &fileName, IArchiveOpenCallback *openArchiveCallback)
{
  CInFileStream *inStreamSpec = new CInFileStream;
  CMyComPtr<IInStream> inStream(inStreamSpec);
  inStreamSpec->Open(fileName);
  return archive->Open(inStream, &kMaxCheckStartPosition, openArchiveCallback);
}

#ifndef _SFX
static inline bool TestSignature(const Byte *p1, const Byte *p2, size_t size)
{
  for (size_t i = 0; i < size; i++)
    if (p1[i] != p2[i])
      return false;
  return true;
}
#endif

HRESULT OpenArchive(
    CCodecs *codecs,
    int arcTypeIndex,
    IInStream *inStream,
    const UString &fileName,
    IInArchive **archiveResult,
    int &formatIndex,
    UString &defaultItemName,
    IArchiveOpenCallback *openArchiveCallback)
{
  *archiveResult = NULL;
  UString extension;
  {
    int dotPos = fileName.ReverseFind(L'.');
    if (dotPos >= 0)
      extension = fileName.Mid(dotPos + 1);
  }
  CIntVector orderIndices;
  if (arcTypeIndex >= 0)
    orderIndices.Add(arcTypeIndex);
  else
  {

  int i;
  int numFinded = 0;
  for (i = 0; i < codecs->Formats.Size(); i++)
    if (codecs->Formats[i].FindExtension(extension) >= 0)
      orderIndices.Insert(numFinded++, i);
    else
      orderIndices.Add(i);
  
  #ifndef _SFX
  if (numFinded != 1)
  {
    CIntVector orderIndices2;
    CByteBuffer byteBuffer;
    const size_t kBufferSize = (1 << 21);
    byteBuffer.SetCapacity(kBufferSize);
    RINOK(inStream->Seek(0, STREAM_SEEK_SET, NULL));
    size_t processedSize = kBufferSize;
    RINOK(ReadStream(inStream, byteBuffer, &processedSize));
    if (processedSize == 0)
      return S_FALSE;

    const Byte *buf = byteBuffer;
    Byte hash[1 << 16];
    memset(hash, 0xFF, 1 << 16);
    Byte prevs[256];
    if (orderIndices.Size() > 255)
      return S_FALSE;
    int i;
    for (i = 0; i < orderIndices.Size(); i++)
    {
      const CArcInfoEx &ai = codecs->Formats[orderIndices[i]];
      const CByteBuffer &sig = ai.StartSignature;
      if (sig.GetCapacity() < 2)
        continue;
      UInt32 v = sig[0] | ((UInt32)sig[1] << 8);
      prevs[i] = hash[v];
      hash[v] = (Byte)i;
    }

    processedSize--;
    for (UInt32 pos = 0; pos < processedSize; pos++)
    {
      for (; pos < processedSize && hash[buf[pos] | ((UInt32)buf[pos + 1] << 8)] == 0xFF; pos++);
      if (pos == processedSize)
        break;
      UInt32 v = buf[pos] | ((UInt32)buf[pos + 1] << 8);
      Byte *ptr = &hash[v];
      int i = *ptr;
      do
      {
        int index = orderIndices[i];
        const CArcInfoEx &ai = codecs->Formats[index];
        const CByteBuffer &sig = ai.StartSignature;
        if (sig.GetCapacity() != 0 && pos + sig.GetCapacity() <= processedSize + 1)
          if (TestSignature(buf + pos, sig, sig.GetCapacity()))
          {
            orderIndices2.Add(index);
            orderIndices[i] = 0xFF;
            *ptr = prevs[i];
          }
        ptr = &prevs[i];
        i = *ptr;
      }
      while (i != 0xFF);
    }
    
    for (i = 0; i < orderIndices.Size(); i++)
    {
      int val = orderIndices[i];
      if (val != 0xFF)
        orderIndices2.Add(val);
    }
    orderIndices = orderIndices2;

    if (orderIndices.Size() >= 2)
    {
      int isoIndex = codecs->FindFormatForArchiveType(L"iso");
      int udfIndex = codecs->FindFormatForArchiveType(L"udf");
      int iIso = -1;
      int iUdf = -1;
      for (int i = 0; i < orderIndices.Size(); i++)
      {
        if (orderIndices[i] == isoIndex) iIso = i;
        if (orderIndices[i] == udfIndex) iUdf = i;
      }
      if (iUdf == iIso + 1)
      {
        orderIndices[iUdf] = isoIndex;
        orderIndices[iIso] = udfIndex;
      }
    }
  }
  else if (extension == L"000" || extension == L"001")
  {
    CByteBuffer byteBuffer;
    const size_t kBufferSize = (1 << 10);
    byteBuffer.SetCapacity(kBufferSize);
    Byte *buffer = byteBuffer;
    RINOK(inStream->Seek(0, STREAM_SEEK_SET, NULL));
    size_t processedSize = kBufferSize;
    RINOK(ReadStream(inStream, buffer, &processedSize));
    if (processedSize >= 16)
    {
      Byte kRarHeader[] = {0x52 , 0x61, 0x72, 0x21, 0x1a, 0x07, 0x00};
      if (TestSignature(buffer, kRarHeader, 7) && buffer[9] == 0x73 && (buffer[10] & 1) != 0)
      {
        for (int i = 0; i < orderIndices.Size(); i++)
        {
          int index = orderIndices[i];
          const CArcInfoEx &ai = codecs->Formats[index];
          if (ai.Name.CompareNoCase(L"rar") != 0)
            continue;
          orderIndices.Delete(i--);
          orderIndices.Insert(0, index);
          break;
        }
      }
    }
  }
  #endif
  }

  for(int i = 0; i < orderIndices.Size(); i++)
  {
    inStream->Seek(0, STREAM_SEEK_SET, NULL);

    CMyComPtr<IInArchive> archive;

    formatIndex = orderIndices[i];
    RINOK(codecs->CreateInArchive(formatIndex, archive));
    if (!archive)
      continue;

    #ifdef EXTERNAL_CODECS
    {
      CMyComPtr<ISetCompressCodecsInfo> setCompressCodecsInfo;
      archive.QueryInterface(IID_ISetCompressCodecsInfo, (void **)&setCompressCodecsInfo);
      if (setCompressCodecsInfo)
      {
        RINOK(setCompressCodecsInfo->SetCompressCodecsInfo(codecs));
      }