As you say it is an LZ77 style format, however I could not find a specific algorithm which it matches. The compressed data forms a number of blocks, each of which contain at least one of some data, or some back references.
Format
Based on the code I've put together a listing of the data structure of the compressed data.
Block
The format of each block is as follows:
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)
Header
The header is as follows:
Section | Length
-----------------------|-------
Num Back References | 3 bits
Data Length | 5 bits
Additional Data Length | 0 to 2 Bytes
The number of back references is encoded into the first 3 bits as a 1 indexed number, allowing a number from 1 (0b000) to 8 (0b111).
In the case that more than 8 back references are required a data length of 0 can be set so you can have several consecutive blocks containing only back references.
The data length is encoded into the next 5 bits.
If the data length is less than 0x1E (30) then it is encoded directly into the top 5 bits of the header.
If it is between 0x1E and 0x11E (286) then a single additional byte will be used, this byte should be the length of the data - 0x11E.
If it is between 0x11E and 0x1011D (65821) then two additional bytes are used as a 16 bit number, which should be the length of the data - 0x11E.
If the data length is the maximum possible (0x1011D) then the number of back references is reduced by one, allowing 0 back references. This allows consecutive data sections without back references.
Back reference
The format of the back references is similar to that of the header:
Section | Length
-----------------------|-------
Data Length | 3 bits
Data Distance | 5 bits
Additional Data Length | 0 to 1 Byte
Additional Distance | 0 to 2 Bytes
The length of data (in bytes) to which the reference refers is encoded into the first 3 bits, allowing length of 0 - 7.
If the length is greater than 7 then these 3 bits are set to 0 and an additional byte is added, containing the length - 7, this allows lengths of up to 262 bytes.
The distance represents the position of the back reference, in bytes back from the current end of the decompressed data. The distance and additional distance bytes are calculated in the same way as the Data Length in the header.
When set, each back reference will copy the calculated data length in bytes from current_position - distance - 1 to the output stream.
There is a special case of a back reference with the length and additional length set to 0. This signifies the end of the stream, and the decompressor will return.
Reasoning
The overall format of a block is reasonably evident from the code, however didn't really make sense until I'd worked out the reasoning behind the magic numbers.
The interesting thing here was the special case of distance = 0x1011D.
To get to the branch which checks for that distance the distance from the intial distance = temp >> 3; must be greater than 0x1E, so it must be 0x1F, as no other value above 0x1E would fit in the top 5 bits of temp.
With this information we can calculate the necessary values of the next 2 bytes (a, and b):
0x1011D = 0x1F + a + (b << 8) + 0xFF
0x1001E = 0x1F + a + (b << 8)
0x0FFFF = a + (b << 8)
As a and b are 8 bit numbers they must necessarily both be 0xFF.
Thus 0x1011D is the largest possible value for distance at that point.
The reasoning for the length-- associated with the conditional becomes apparent: This allows for raw data blocks with no back references, for use in cases such as images or other poorly compressible data.
Other than this, the range of numbers that the Data Length supports can be easily calculated by considering the result of setting temp to 0b11111??? and 0b11110??? and checking the maximum and minimum values of the following two bytes.
Having understood the block header format the back reference format is fairly easy to understand, the main gotcha being that length = 0 with a following byte of 0 ends the stream.
Writing a counterpart compression algorithm
If you do not need the files to fit in the same space as the original files then the easiest way to "compress" your own files is to ignore the actual compression features of the format, and do the bare minimum of creating maximum size data blocks until the final block, which will have a single back reference, that being the end of stream signal. A quick implementation of this follows.
#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;
}
Compile: clang++ --std=c++14 -o fake_compress fake_compress.cpp
And run:
$ ./fake_compress havok.xml
Compressing havok.xml
Compressed from 137261 to 137272
Saved as havok.xml.compres
Regenerated file matches original.
