rar3vm.cpp

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

            else if (Distance >= 8)
              Distance -= 16;
            Distance += prg->Commands.Size() - 1;
          }
          cmd->Op1.Data = Distance;
        }
      }
    }
    if (cmd->ByteMode)
    {
      switch (cmd->OpCode)
      {
        case CMD_MOV: cmd->OpCode = CMD_MOVB; break;
        case CMD_CMP: cmd->OpCode = CMD_CMPB; break;
        case CMD_ADD: cmd->OpCode = CMD_ADDB; break;
        case CMD_SUB: cmd->OpCode = CMD_SUBB; break;
        case CMD_INC: cmd->OpCode = CMD_INCB; break;
        case CMD_DEC: cmd->OpCode = CMD_DECB; break;
        case CMD_XOR: cmd->OpCode = CMD_XORB; break;
        case CMD_AND: cmd->OpCode = CMD_ANDB; break;
        case CMD_OR: cmd->OpCode = CMD_ORB; break;
        case CMD_TEST: cmd->OpCode = CMD_TESTB; break;
        case CMD_NEG: cmd->OpCode = CMD_NEGB; break;
        case CMD_SHL: cmd->OpCode = CMD_SHLB; break;
        case CMD_SHR: cmd->OpCode = CMD_SHRB; break;
        case CMD_SAR: cmd->OpCode = CMD_SARB; break;
        case CMD_MUL: cmd->OpCode = CMD_MULB; break;
      }
    }
  }
}

#ifdef RARVM_STANDARD_FILTERS

enum EStandardFilter
{
  SF_E8,
  SF_E8E9,
  SF_ITANIUM,
  SF_RGB,
  SF_AUDIO,
  SF_DELTA,
  SF_UPCASE
};

struct StandardFilterSignature
{
  UInt32 Length;
  UInt32 CRC;
  EStandardFilter Type;
}
kStdFilters[]=
{
   53, 0xad576887, SF_E8,
   57, 0x3cd7e57e, SF_E8E9,
  120, 0x3769893f, SF_ITANIUM,
   29, 0x0e06077d, SF_DELTA,
  149, 0x1c2c5dc8, SF_RGB,
  216, 0xbc85e701, SF_AUDIO,
   40, 0x46b9c560, SF_UPCASE
};

static int FindStandardFilter(const Byte *code, UInt32 codeSize)
{
  UInt32 crc = CrcCalc(code, codeSize);
  for (int i = 0; i < sizeof(kStdFilters) / sizeof(kStdFilters[0]); i++)
  {
    StandardFilterSignature &sfs = kStdFilters[i];
    if (sfs.CRC == crc && sfs.Length == codeSize)
      return i;
  }
  return -1;
}

#endif

void CVm::PrepareProgram(const Byte *code, UInt32 codeSize, CProgram *prg)
{
  Byte xorSum = 0;
  for (UInt32 i = 1; i < codeSize; i++)
    xorSum ^= code[i];

  prg->Commands.Clear();
  #ifdef RARVM_STANDARD_FILTERS
  prg->StandardFilterIndex = -1;
  #endif

  if (xorSum == code[0] && codeSize > 0)
  {
    #ifdef RARVM_STANDARD_FILTERS
    prg->StandardFilterIndex = FindStandardFilter(code, codeSize);
    if (prg->StandardFilterIndex >= 0)
      return;
    #endif
    // 1 byte for checksum
    ReadVmProgram(code + 1, codeSize - 1, prg);
  }
  prg->Commands.Add(CCommand());
  CCommand *cmd = &prg->Commands.Back();
  cmd->OpCode = CMD_RET;
}

void CVm::SetMemory(UInt32 pos, const Byte *data, UInt32 dataSize)
{
  if (pos < kSpaceSize && data != Mem + pos)
    memmove(Mem + pos, data, MyMin(dataSize, kSpaceSize - pos));
}

#ifdef RARVM_STANDARD_FILTERS

static void E8E9Decode(Byte *data, UInt32 dataSize, UInt32 fileOffset, bool e9)
{
  if (dataSize <= 4)
    return;
  dataSize -= 4;
  const UInt32 kFileSize = 0x1000000;
  Byte cmpByte2 = (e9 ? 0xE9 : 0xE8);
  for (UInt32 curPos = 0; curPos < dataSize;)
  {
    Byte curByte = *(data++);
    curPos++;
    if (curByte == 0xE8 || curByte == cmpByte2)
    {
      UInt32 offset = curPos + fileOffset;
      UInt32 addr = (Int32)GetValue32(data);
      if (addr < kFileSize)
        SetValue32(data, addr - offset);
      else if ((Int32)addr < 0 && (Int32)(addr + offset) >= 0)
        SetValue32(data, addr + kFileSize);
      data += 4;
      curPos += 4;
    }
  }
}

static inline UInt32 ItaniumGetOpType(const Byte *data, int bitPos)
{
  return (data[(unsigned int)bitPos >> 3] >> (bitPos & 7)) & 0xF;
}


static void ItaniumDecode(Byte *data, UInt32 dataSize, UInt32 fileOffset)
{
  UInt32 curPos = 0;
  fileOffset >>= 4;
  while (curPos < dataSize - 21)
  {
    int b = (data[0] & 0x1F) - 0x10;
    if (b >= 0)
    {
      static Byte kCmdMasks[16] = {4,4,6,6,0,0,7,7,4,4,0,0,4,4,0,0};
      Byte cmdMask = kCmdMasks[b];
      if (cmdMask != 0)
        for (int i = 0; i < 3; i++)
          if (cmdMask & (1 << i))
          {
            int startPos = i * 41 + 18;
            if (ItaniumGetOpType(data, startPos + 24) == 5)
            {
              const UInt32 kMask = 0xFFFFF;
              Byte *p = data + ((unsigned int)startPos >> 3);
              UInt32 bitField =  ((UInt32)p[0]) | ((UInt32)p[1] <<  8) | ((UInt32)p[2] << 16);
              int inBit = (startPos & 7);
              UInt32 offset = (bitField >> inBit) & kMask;
              UInt32 andMask = ~(kMask << inBit);
              bitField = ((offset - fileOffset) & kMask) << inBit;
              for (int j = 0; j < 3; j++)
              {
                p[j] &= andMask;
                p[j] |= bitField;
                andMask >>= 8;
                bitField >>= 8;
              }
            }
          }
    }
    data += 16;
    curPos += 16;
    fileOffset++;
  }
}

static void DeltaDecode(Byte *data, UInt32 dataSize, UInt32 numChannels)
{
  UInt32 srcPos = 0;
  UInt32 border = dataSize * 2;
  for (UInt32 curChannel = 0; curChannel < numChannels; curChannel++)
  {
    Byte prevByte = 0;
    for (UInt32 destPos = dataSize + curChannel; destPos < border; destPos += numChannels)
      data[destPos] = (prevByte = prevByte - data[srcPos++]);
  }
}

static void RgbDecode(Byte *srcData, UInt32 dataSize, UInt32 width, UInt32 posR)
{
  Byte *destData = srcData + dataSize;
  const UInt32 numChannels = 3;
  for (UInt32 curChannel = 0; curChannel < numChannels; curChannel++)
  {
    Byte prevByte = 0;
    
    for (UInt32 i = curChannel; i < dataSize; i+= numChannels)
    {
      unsigned int predicted;
      if (i < width)
        predicted = prevByte;
      else
      {
        unsigned int upperLeftByte = destData[i - width];
        unsigned int upperByte = destData[i - width + 3];
        predicted = prevByte + upperByte - upperLeftByte;
        int pa = abs((int)(predicted - prevByte));
        int pb = abs((int)(predicted - upperByte));
        int pc = abs((int)(predicted - upperLeftByte));
        if (pa <= pb && pa <= pc)
          predicted = prevByte;
        else
          if (pb <= pc)
            predicted = upperByte;
          else
            predicted = upperLeftByte;
      }
      destData[i] = prevByte = (Byte)(predicted - *(srcData++));
    }
  }
  if (dataSize < 3)
    return;
  for (UInt32 i = posR, border = dataSize - 2; i < border; i += 3)
  {
    Byte g = destData[i + 1];
    destData[i] = destData[i] + g;
    destData[i + 2] = destData[i + 2] + g;
  }
}

static void AudioDecode(Byte *srcData, UInt32 dataSize, UInt32 numChannels)
{
  Byte *destData = srcData + dataSize;
  for (UInt32 curChannel = 0; curChannel < numChannels; curChannel++)
  {
    UInt32 prevByte = 0, prevDelta = 0, dif[7];
    Int32 D1 = 0, D2 = 0, D3;
    Int32 K1 = 0, K2 = 0, K3 = 0;
    memset(dif, 0, sizeof(dif));
    
    for (UInt32 i = curChannel, byteCount = 0; i < dataSize; i += numChannels, byteCount++)
    {
      D3 = D2;
      D2 = prevDelta - D1;
      D1 = prevDelta;
      
      UInt32 predicted = 8 * prevByte + K1 * D1 + K2 * D2 + K3 * D3;
      predicted = (predicted >> 3) & 0xFF;
      
      UInt32 curByte = *(srcData++);
      
      predicted -= curByte;
      destData[i] = (Byte)predicted;
      prevDelta = (UInt32)(Int32)(signed char)(predicted - prevByte);
      prevByte = predicted;
      
      Int32 D = ((Int32)(signed char)curByte) << 3;
      
      dif[0] += abs(D);
      dif[1] += abs(D - D1);
      dif[2] += abs(D + D1);
      dif[3] += abs(D - D2);
      dif[4] += abs(D + D2);
      dif[5] += abs(D - D3);
      dif[6] += abs(D + D3);
      
      if ((byteCount & 0x1F) == 0)
      {
        UInt32 minDif = dif[0], numMinDif = 0;
        dif[0] = 0;
        for (int j = 1; j < sizeof(dif) / sizeof(dif[0]); j++)
        {
          if (dif[j] < minDif)
          {
            minDif = dif[j];
            numMinDif = j;
          }
          dif[j] = 0;
        }
        switch (numMinDif)
        {
          case 1: if (K1 >= -16) K1--; break;
          case 2: if (K1 <   16) K1++; break;
          case 3: if (K2 >= -16) K2--; break;
          case 4: if (K2 <   16) K2++; break;
          case 5: if (K3 >= -16) K3--; break;
          case 6: if (K3 <   16) K3++; break;
        }
      }
    }
  }
}

static UInt32 UpCaseDecode(Byte *data, UInt32 dataSize)
{
  UInt32 srcPos = 0, destPos = dataSize;
  while (srcPos < dataSize)
  {
    Byte curByte = data[srcPos++];
    if (curByte == 2 && (curByte = data[srcPos++]) != 2)
      curByte -= 32;
    data[destPos++] = curByte;
  }
  return destPos - dataSize;
}

void CVm::ExecuteStandardFilter(int filterIndex)
{
  UInt32 dataSize = R[4];
  if (dataSize >= kGlobalOffset)
    return;
  EStandardFilter filterType = kStdFilters[filterIndex].Type;

  switch (filterType)
  {
    case SF_E8:
    case SF_E8E9:
      E8E9Decode(Mem, dataSize, R[6], (filterType == SF_E8E9));
      break;
    case SF_ITANIUM:
      ItaniumDecode(Mem, dataSize, R[6]);
      break;
    case SF_DELTA:
      if (dataSize >= kGlobalOffset / 2)
        break;
      SetBlockPos(dataSize);
      DeltaDecode(Mem, dataSize, R[0]);
      break;
    case SF_RGB:
      if (dataSize >= kGlobalOffset / 2)
        break;
      {
        UInt32 width = R[0];
        if (width <= 3)
          break;
        SetBlockPos(dataSize);
        RgbDecode(Mem, dataSize, width, R[1]);
      }
      break;
    case SF_AUDIO:
      if (dataSize >= kGlobalOffset / 2)
        break;
      SetBlockPos(dataSize);
      AudioDecode(Mem, dataSize, R[0]);
      break;
    case SF_UPCASE:
      if (dataSize >= kGlobalOffset / 2)
        break;
      UInt32 destSize = UpCaseDecode(Mem, dataSize);
      SetBlockSize(destSize);
      SetBlockPos(dataSize);
      break;
  }
}

#endif

}}}