正如您所说，它是一种 LZ77 样式格式，但是我找不到与之匹配的特定算法。压缩数据形成多个块，每个块包含一些数据或一些反向引用中的至少一个。
格式
根据代码，我将压缩数据的数据结构列表放在一起。
堵塞
每个块的格式如下：
Section | Length
-----------------------|-------
Header | 1 to 3 Bytes (see header explanation)
Data | 0 to 0x1011D (65821) Bytes
Back references | 0 to 8 occurences of 1 to 4 Bytes (see back reference explanation)
标题
标题如下：
Section | Length
-----------------------|-------
Num Back References | 3 bits
Data Length | 5 bits
Additional Data Length | 0 to 2 Bytes
反向引用的数量被编码到前 3 位作为 1 索引数字，允许从 1 ( 0b000) 到 8 ( 0b111) 的数字。在需要超过 8 个反向引用的情况下，可以将数据长度设置为 0，这样您就可以拥有多个仅包含反向引用的连续块。
数据长度被编码为接下来的 5 位。如果数据长度小于0x1E(30)，则将其直接编码到报头的前 5 位。如果它在0x1E和0x11E(286)之间，那么将使用一个额外的字节，这个字节应该是数据的长度 - 0x11E。如果它在0x11E和0x1011D(65821)之间，则使用两个额外字节作为 16 位数字，这应该是数据的长度 - 0x11E。
如果数据长度是最大可能的 ( 0x1011D)，则反向引用的数量减少 1，允许 0 个反向引用。这允许没有反向引用的连续数据段。
回参考
反向引用的格式类似于标题的格式：
Section | Length
-----------------------|-------
Data Length | 3 bits
Data Distance | 5 bits
Additional Data Length | 0 to 1 Byte
Additional Distance | 0 to 2 Bytes
引用引用的数据长度（以字节为单位）被编码为前 3 位，允许长度为 0 - 7。如果长度大于 7，则这 3 位设置为 0，并添加一个额外的字节，包含长度 - 7，这允许最多 262 个字节的长度。
距离表示向后引用的位置，以从解压缩数据的当前结尾向后的字节为单位。距离和附加距离字节的计算方式与标头中的数据长度相同。
设置后，每个反向引用都会将计算出的数据长度（以字节current_position - distance - 1为单位）复制到输出流。
有一种特殊情况，即长度和附加长度设置为 0 的反向引用。这表示流结束，解压器将返回。
推理
从代码中可以很明显地看出块的整体格式，但是在我弄清楚幻数背后的推理之前并没有真正的意义。
这里有趣的是distance = 0x1011D. 要到达检查该距离的分支，与初始值的距离distance = temp >> 3;必须大于0x1E，因此必须大于0x1F，因为上面没有其他值0x1E适合temp. 有了这些信息，我们可以计算接下来的 2 个字节（a， 和b）的必要值：
0x1011D = 0x1F + a + (b << 8) + 0xFF
0x1001E = 0x1F + a + (b << 8)
0x0FFFF = a + (b << 8)
由于a和b是 8 位数字，它们必须都是0xFF. 因此0x1011D是该distance点的最大可能值。
length--与条件相关的推理变得明显：这允许没有反向引用的原始数据块，用于图像或其他可压缩性较差的数据等情况。
除此之外，Data Length 支持的数字范围可以通过考虑设置temp为0b11111???和的结果0b11110???并检查以下两个字节的最大值和最小值来轻松计算。
理解了块头格式后，反向引用格式就很容易理解了，主要的问题是，length = 0后面的字节0结束了流。
编写对应的压缩算法
如果您不需要将文件与原始文件放在相同的空间中，那么“压缩”您自己的文件的最简单方法是忽略格式的实际压缩功能，并尽可能少地创建最大大小的数据块直到最后一个块，它将有一个单一的反向引用，即流信号的结束。下面是一个快速实现。
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <deque>
#include <fstream>
#include <iterator>
unsigned int decompress(uint8_t *decompressed, uint8_t *compressed)
{
uint32_t distance, length, i, j;
uint8_t temp, *compressed_ptr = compressed,
*decompressed_ptr = decompressed, *backwards_ptr = NULL;
while (1)
{
temp = *(compressed_ptr++);
length = (temp & 7) + 1;
distance = temp >> 3;
if (distance == 0x1E)
distance = *(compressed_ptr++) + 0x1E;
else if (distance > 0x1E)
{
distance += *compressed_ptr;
distance += (*(++compressed_ptr) << 8) + 0xFF;
compressed_ptr++;
if (distance == 0x1011D)
length--;
}
if (distance != 0)
{
std::memcpy(decompressed_ptr, compressed_ptr, distance);
decompressed_ptr += distance;
compressed_ptr += distance;
}
for (i = length; i > 0; i--)
{
temp = *(compressed_ptr++);
length = temp & 7;
distance = temp >> 3;
if (length == 0)
{
length = *(compressed_ptr++);
if (length == 0)
{
return (uintptr_t)decompressed_ptr -
(uintptr_t)decompressed;
}
length += 7;
}
if (distance == 0x1E)
distance = *(compressed_ptr++) + 0x1E;
else if (distance > 0x1E)
{
distance += *compressed_ptr;
distance += (*(++compressed_ptr) << 8) + 0xFF;
compressed_ptr++;
}
backwards_ptr = decompressed_ptr - distance - 1;
for (j = length; j > 0; j--)
*(decompressed_ptr++) = *(backwards_ptr++);
}
}
}
std::vector<uint8_t> compress(const std::vector<uint8_t>& input)
{
const uint32_t max_distance = 0x1011D;
std::vector<uint8_t> output;
auto input_it = input.begin();
// Repeat as many max length blocks as we can
auto remaining_input = std::distance(input_it, input.end());
while(remaining_input > max_distance)
{
output.push_back(0xF8);
output.push_back(0xFF);
output.push_back(0xFF);
std::copy(input_it, input_it + max_distance, std::back_inserter(output));
input_it += max_distance;
remaining_input = std::distance(input_it, input.end());
}
// Add a final block with the remaining data
if(remaining_input > 0x11D)
{
output.push_back(0xF8);
const uint16_t header_bytes = remaining_input - 0x11E;
output.push_back(header_bytes & 0xFF);
output.push_back(header_bytes >> 8);
std::copy(input_it, input.end(), std::back_inserter(output));
}
else if(remaining_input > 0x1D)
{
output.push_back(0xF0);
const uint8_t header_byte = remaining_input - 0x1E;
output.push_back(header_byte);
std::copy(input_it, input.end(), std::back_inserter(output));
}
else
{
const uint8_t header_byte = remaining_input << 3;
output.push_back(header_byte);
std::copy(input_it, input.end(), std::back_inserter(output));
}
// Add a special case 0 length back reference to end the stream
output.push_back(0x00);
output.push_back(0x00);
return output;
}
int main(int argc, char* argv[])
{
std::deque<std::string> args(argv, argv+argc);
args.pop_front();
if(args.empty())
{
std::cerr << "No input files!" << std::endl;
return 1;
}
for(const auto& filename : args)
{
std::ifstream in_file(filename, std::ios::in | std::ios::binary);
if(!in_file.good())
{
std::cerr << "Bad input file: " << filename << std::endl;
return 1;
}
std::cout << "Compressing " << filename << std::endl;
std::vector<uint8_t> input(
(std::istreambuf_iterator<char>(in_file)),
(std::istreambuf_iterator<char>())
);
auto compressed = compress(input);
std::cout << "Compressed from " << input.size() << " to " << compressed.size() << std::endl;
const std::string new_filename = filename + ".compres";
std::ofstream out_file(new_filename);
out_file.write((char*)compressed.data(), compressed.size());
out_file.close();
std::cout << "Saved as " << new_filename << std::endl;
const int buffer_length = 2000000;
uint8_t buffer[buffer_length];
const int size = decompress(buffer, compressed.data());
std::vector<uint8_t> regenerated;
regenerated.assign(buffer, buffer + size);
if(regenerated == input)
std::cout << "Regenerated file matches original." << std::endl;
else
std::cout << "Regenerated file DOES NOT MATCH original!" << std::endl;
}
return 0;
}
编译： clang++ --std=c++14 -o fake_compress fake_compress.cpp
并运行：
$ ./fake_compress havok.xml
Compressing havok.xml
Compressed from 137261 to 137272
Saved as havok.xml.compres
Regenerated file matches original.