7

I've reversed the following decompression algorithm from a game. It appears to be some variant of LZ77, however none of the descriptions of variants seem quite close enough what I've got. Is this a specific flavor of LZ77, and if not, how would I go about creating an equivalent compression method? The files have no header.

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)
        {
            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++);
        }
    }
}
8

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.
|improve this answer|||||
2

Most general purpose LZ77-like formats are optimized for efficient insertion of individual literal characters, and for the arbitrary sequence of literals and backward references - this is useful to achieve good compression rates on natural language text as well on text-like binary data (executable code). They also have a notion of a sliding dictionary window to handle files or streams of arbitrary sizes.

The routine in your question appears to handle a format adapted specifically for in-memory data (note the absence of a sliding window) with many (up to 8 in a row) consecutive references to the decompressed buffer, interspersed with occasional long strings that have to be copied literally.

Note that there are only two ways to add characters to the decompressed stream: by literal copying using a memcpy call, and by copying in a loop using the backwards pointer. In other words, these two modes of operation are "copying a (fairly long) dictionary from the compressed stream", and "reading references to the dictionary from the compressed stream and copying strings from the dictionary". There is no special provision for individual literal characters.

Any straightforward implementation of an LZ77 compression algorithm (a function of a character string into a stream of tokens "literal character" or "distance/length") would do. Then you'll be able to write a program to pack these tokens according to the limitation of the format (pay attention to the magic value 0x1011D).

Alternatively, as you're unlikely to be limited by the media size, you may avoid the need to do any actual compression (the analog of compression level 0). For your purposes, it could be enough to represent all the data as a sequence of long literals, using the "distance" field for the length of literal string and setting the "length" field to 0 to indicate that there are no dictionary references following the literal string. Repeat until the data is exhausted.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.