Asobo LZ Compression

Custom LZRS Compression

FUEL uses a byte-aligned, sliding window Lempel–Ziv-Reed-Solomon (LZRS) variant with 32-bit control flags.

The same compression method is used in most Asobo games. At this time I can confirm it is used in Ratatouille and WALL-E. The WALL-E (Mac) debug symbols use the UnPack_Z::DecodeRS and Pack_Z::EncodeRS method names for these functions. Future games may use different methods, for example, A Plague Tale games use LZ4. A Python implementation of the decompression method is available in the fmt_fuel repository. A Rust implementation of the decompression and compression methods is available in the dpc repository.

void lzrs_fuel_decompress(const std::uint8_t* compressed_buffer_ptr, std::uint32_t compressed_buffer_size, std::uint8_t* decompressed_buffer_ptr, std::uint32_t decompressed_buffer_size, bool is_in_place)
{
    // Magic Numbers
    constexpr std::uint32_t WINDOW_LOG = 0xe;
    constexpr std::uint32_t WINDOW_MASK = 0x3fff;

    std::uint8_t* end_ptr = decompressed_buffer_ptr + decompressed_buffer_size;

    while (true)
    {
        std::uint32_t flag = _byteswap_ulong(*(std::uint32_t*)compressed_buffer_ptr); // read as big endian
        std::uint8_t len = flag & 0x3; // 0b11 [0-3]
        std::uint8_t temp_shift = WINDOW_LOG - len;
        std::uint32_t temp_mask = WINDOW_MASK >> len;
        compressed_buffer_ptr += 4;

        for (std::uint8_t i = 0; i < 30; ++i)
        {
            if ((flag & 0x80000000) != 0)
            {
                std::uint16_t temp = _byteswap_ushort(*(std::uint16_t*)compressed_buffer_ptr); // read as big endian
                compressed_buffer_ptr += 2;

                std::uint8_t* window_ptr = decompressed_buffer_ptr - ((temp & temp_mask) + 1);
                for (std::uint32_t length = (temp >> temp_shift) + 3; length > 0; --length)
                {
                    *(decompressed_buffer_ptr++) = *(window_ptr++);
                }
            }
            else
            {
                *(decompressed_buffer_ptr++) = *(compressed_buffer_ptr++);
            }

            if ((decompressed_buffer_ptr == end_ptr) || (is_in_place && (decompressed_buffer_ptr > compressed_buffer_ptr)))
            {
                return;
            }

            flag <<= 1;
        }
    }
}

#define PACKET_SIZE (0x8000U)
#define LOOKUP_TABLE_SIZE (1 << (sizeof(std::uint16_t) * CHAR_BIT))

struct PacketMatch
{
    std::int32_t length = 0;
    std::int32_t data = 0;
};

struct Packet
{
    std::int32_t match_length = 0;
    std::int32_t total_length = 0;
    std::vector<PacketMatch> matches = {};
};

struct Match
{
    const std::uint8_t* ptr = nullptr;
    Match* prev = nullptr;
    Match* next = nullptr;

    void orphan()
    {
        prev->next = nullptr;
        prev = nullptr;
    }

    void push_back(Match* node)
    {
        node->prev = prev;
        if (node->prev) node->prev->next = node;
        node->next = this;
        node->next->prev = node;
    }
};

bool encode_packet(const std::uint8_t* uncompressed_buffer_ptr, Packet& packet, std::uint32_t window_index, const std::uint8_t* const uncompressed_buffer, const std::uint8_t* const uncompressed_buffer_end, Match* const g_window_buffer)
{
    std::uint32_t remaining_length = (1 << packet.match_length) + 2;
    std::uint32_t v20 = 0x10000 >> packet.match_length;

    packet.matches.clear();
    for (std::uint32_t i = 0; i != 30; ++i)
    {
        const std::uint8_t* v5 = std::max(uncompressed_buffer, uncompressed_buffer_ptr - v20);

        remaining_length = std::min(remaining_length, (std::uint32_t)(uncompressed_buffer_end - uncompressed_buffer_ptr));

        if (remaining_length <= 2)
        {
            packet.total_length++;
            packet.matches.push_back({ -1, *uncompressed_buffer_ptr++ });
            window_index++;
        }
        else
        {
            const std::uint8_t* ptr = nullptr;

            std::int32_t match_length = 2;
            for (Match* cur = g_window_buffer[window_index].prev; cur && cur->ptr >= v5; cur = cur->prev)
            {
                if (uncompressed_buffer_ptr[2] == cur->ptr[2])
                {
                    std::uint32_t j;
                    for (j = 3; cur->ptr[j] == uncompressed_buffer_ptr[j] && remaining_length != j; ++j)
                        ;

                    if (match_length < j)
                    {
                        if (remaining_length == j)
                        {
                            ptr = cur->ptr;
                            match_length = remaining_length;
                            break;
                        }
                        match_length = j;
                        ptr = cur->ptr;
                    }
                }
            }

            if (match_length == 2)
            {
                packet.total_length++;
                packet.matches.push_back({ -1, *uncompressed_buffer_ptr++ });
                window_index++;
            }
            else
            {
                packet.total_length += match_length;
                packet.matches.push_back({ match_length - 3, (std::int32_t)(uncompressed_buffer_ptr - ptr) });
                uncompressed_buffer_ptr += match_length;
                window_index += match_length;
            }
        }

        window_index = window_index % PACKET_SIZE;

        if (uncompressed_buffer_ptr >= uncompressed_buffer_end)
        {
            return false;
        }
    }

    return true;
}

std::uint32_t lzrs_fuel_compress(const std::uint8_t* uncompressed_buffer, std::uint8_t* compressed_buffer, std::uint32_t uncompressed_buffer_size, std::uint32_t compressed_buffer_size)
{
    Match* g_window_buffer = new Match[PACKET_SIZE];
    Match* short_lookup = new Match[LOOKUP_TABLE_SIZE];

    *reinterpret_cast<std::uint32_t*>(compressed_buffer) = uncompressed_buffer_size;
    std::uint8_t* compressed_buffer_ptr = compressed_buffer + 8;

    const std::uint32_t WINDOW_SIZE = std::min(uncompressed_buffer_size, PACKET_SIZE);

    const std::uint8_t* const uncompressed_buffer_end = uncompressed_buffer + uncompressed_buffer_size;

    Packet packets[4];
    packets[0].match_length = 2;
    packets[1].match_length = 3;
    packets[2].match_length = 4;
    packets[3].match_length = 5;

    std::uint32_t window_index = 0;

    for (std::uint32_t i = 0; i < WINDOW_SIZE; ++i)
    {
        const std::uint8_t* ptr = uncompressed_buffer + i;
        std::uint32_t match_index = _byteswap_ushort(*reinterpret_cast<const std::uint16_t*>(ptr));
        Match& current = g_window_buffer[i];
        Match& next = short_lookup[match_index];
        current.ptr = ptr;
        next.push_back(&current);
    }

    const std::uint8_t* uncompressed_buffer_ptr = uncompressed_buffer;

    std::uint32_t buffer_size_2 = PACKET_SIZE;
    std::int32_t k = 0x7000;

    while (uncompressed_buffer_ptr < uncompressed_buffer_end)
    {
        std::uint8_t len;

        packets[3].total_length = 0;
        packets[2].total_length = 0;
        packets[1].total_length = 0;
        packets[0].total_length = 0;

        if (encode_packet(uncompressed_buffer_ptr, packets[3], window_index, uncompressed_buffer, uncompressed_buffer_end, g_window_buffer) && packets[3].total_length <= 540)
        {
            if (encode_packet(uncompressed_buffer_ptr, packets[2], window_index, uncompressed_buffer, uncompressed_buffer_end, g_window_buffer))
            {
                len = (packets[2].total_length <= packets[3].total_length) + 2;
                if (packets[len].total_length <= 300)
                {
                    if (encode_packet(uncompressed_buffer_ptr, packets[1], window_index, uncompressed_buffer, uncompressed_buffer_end, g_window_buffer))
                    {
                        if (packets[1].total_length > packets[len].total_length)
                        {
                            len = 1;
                        }

                        if (packets[len].total_length <= 180)
                        {
                            encode_packet(uncompressed_buffer_ptr, packets[0], window_index, uncompressed_buffer, uncompressed_buffer_end, g_window_buffer);
                            if (packets[0].total_length >= packets[len].total_length)
                            {
                                len = 0;
                            }
                        }
                    }
                    else
                    {
                        len = 1;
                    }
                }
            }
            else
            {
                len = 2;
            }
        }
        else
        {
            len = 3;
        }

        Packet& currentPacket = packets[len];

        std::uint32_t flag = 0;
        for (std::uint32_t i = 0; i < currentPacket.matches.size(); ++i)
        {
            if (currentPacket.matches[i].length >= 0)
            {
                flag |= 0x80000000U >> i;
            }
        }

        *reinterpret_cast<std::uint32_t*>(compressed_buffer_ptr) = _byteswap_ulong(flag | len);
        compressed_buffer_ptr += 4;

        for (auto match : currentPacket.matches)
        {
            if (match.length == -1)
            {
                *compressed_buffer_ptr++ = match.data;
            }
            else
            {
                *reinterpret_cast<std::uint16_t*>(compressed_buffer_ptr) = _byteswap_ushort(match.data + (match.length << (0xEU - len)) - 1);
                compressed_buffer_ptr += 2;
            }
        }

        uncompressed_buffer_ptr += currentPacket.total_length;

        window_index = (window_index + currentPacket.total_length) % PACKET_SIZE;

        k -= currentPacket.total_length;
        if (k < 0)
        {
            const std::uint32_t WINDOW_SIZE_1 = std::min(uncompressed_buffer_size, buffer_size_2 + 0x1000U);
            for (std::uint32_t i = buffer_size_2; i < WINDOW_SIZE_1; ++i)
            {
                const std::uint8_t* ptr = uncompressed_buffer + i;
                std::uint32_t match_index = _byteswap_ushort(*reinterpret_cast<const std::uint16_t*>(ptr));
                Match& current = g_window_buffer[i % PACKET_SIZE];
                Match& next = short_lookup[match_index];
                current.next->orphan();
                current.ptr = ptr;
                next.push_back(&current);
            }
            k += 0x1000U;
            buffer_size_2 = WINDOW_SIZE_1;
        }
    }

    std::uint32_t compressed_size = compressed_buffer_ptr - compressed_buffer;
    *reinterpret_cast<std::uint32_t*>(compressed_buffer + 4) = compressed_size;

    delete[] g_window_buffer;
    delete[] short_lookup;

    return compressed_size;
}

This alternate compression function has a better compression ratio than the original one used by Asobo.

std::uint32_t lzrs_fuel_compress_alternate(const std::uint8_t* decompressed_buffer, std::uint32_t decompressed_buffer_size, std::uint8_t* compressed_buffer, std::uint32_t compressed_buffer_size)
{
    constexpr std::uint32_t WINDOW_LOG = 14;
    constexpr std::uint32_t WINDOW_MASK = (1 << WINDOW_LOG) - 1;
    constexpr std::uint32_t MATCH_NUM = 30;
    constexpr std::uint32_t MATCH_ITER = 4;
    constexpr std::uint32_t MIN_MATCH_LEN = 3;
    constexpr std::uint32_t MIN_DISTANCE = 1;

    std::uint32_t distances_table[MATCH_NUM][MATCH_ITER]; // distances
    std::uint32_t lengths_table[MATCH_NUM][MATCH_ITER]; // lengths

    const std::uint8_t* decompressed_buffer_ptr = decompressed_buffer;
    const std::uint8_t* decompressed_buffer_end = decompressed_buffer + decompressed_buffer_size;
    std::uint8_t* compressed_buffer_ptr = compressed_buffer;

    while (true)
    {
        if (decompressed_buffer_ptr >= decompressed_buffer_end)
        {
            break;
        }

        const std::uint8_t* decompressed_buffer_ptr_backup = decompressed_buffer_ptr;
        std::uint8_t* pflag = compressed_buffer_ptr;
        compressed_buffer_ptr += 4;
        std::uint32_t opt_flag = 0;
        double opt_rate = 0;

        for (std::uint32_t t = 0; t < MATCH_ITER; t++)
        {
            std::uint32_t flag = 0;
            std::uint32_t ulen = 0;
            std::uint32_t clen = 0;
            decompressed_buffer_ptr = decompressed_buffer_ptr_backup;
            std::uint32_t temp_wlog = WINDOW_LOG - t;
            std::uint32_t temp_mlen = (1 << (16 - temp_wlog)) - 1 + MIN_MATCH_LEN;
            std::uint32_t temp_mask = WINDOW_MASK >> t;

            for (std::uint32_t i = 0; i < MATCH_NUM; i++)
            {
                distances_table[i][t] = 0;
                lengths_table[i][t] = 1;
            }

            for (std::uint32_t i = 0; i < MATCH_NUM; i++)
            {
                if (decompressed_buffer_ptr >= decompressed_buffer_end)
                {
                    break;
                }

                std::uint32_t pos = decompressed_buffer_ptr - decompressed_buffer;
                std::uint32_t k = pos - (temp_mask + MIN_DISTANCE);
                if ((k & 0x80000000) != 0)
                {
                    k = 0;
                }
                std::uint32_t l = decompressed_buffer_end - decompressed_buffer_ptr;
                if (l > temp_mlen)
                {
                    l = temp_mlen;
                }
                std::uint32_t ml = 0; // max match len
                std::uint32_t mj = 0; // max match pos
                std::uint32_t start = pos - 1;
                std::uint32_t end = k - 1;
                std::uint32_t j = start;
                while (j != end)
                {
                    std::uint32_t rr = l;
                    for (std::uint32_t r = 0; r < l; r++)
                    {
                        if (decompressed_buffer_ptr[r] != decompressed_buffer[j + r])
                        {
                            rr = r;
                            break;
                        }
                    }
                    if (rr > ml)
                    {
                        ml = rr;
                        mj = pos - j;
                    }

                    j--;
                }

                if (ml < MIN_MATCH_LEN)
                {
                    // literal
                    ulen += 1;
                    decompressed_buffer_ptr++;
                    clen += 1;
                }
                else
                {
                    // match
                    distances_table[i][t] = mj;
                    lengths_table[i][t] = ml;
                    flag |= 1 << (31 - i);
                    ulen += ml;
                    decompressed_buffer_ptr += ml;
                    clen += 2;
                }

            } // for

            double new_rate = double(ulen) / (4 + clen);

            if (new_rate > opt_rate)
            {
                opt_rate = new_rate;
                opt_flag = flag | t;
            }
        }

        *(std::uint32_t*)pflag = _byteswap_ulong(opt_flag); // write as big endian

        std::uint32_t t = opt_flag & 3;
        decompressed_buffer_ptr = decompressed_buffer_ptr_backup;
        std::uint32_t temp_wlog = WINDOW_LOG - t;
        std::uint32_t temp_mask = WINDOW_MASK >> t;

        for (std::uint32_t i = 0; i < MATCH_NUM; i++)
        {
            if (decompressed_buffer_ptr >= decompressed_buffer_end)
            {
                break;
            }
            if (opt_flag & (1 << (31 - i)))
            {
                // match
                std::uint32_t ml = lengths_table[i][t];
                std::uint32_t mj = distances_table[i][t];
                std::uint16_t c = ((ml - MIN_MATCH_LEN) << temp_wlog) + ((mj - MIN_DISTANCE) & temp_mask);
                *(std::uint16_t*)compressed_buffer_ptr = _byteswap_ushort(c);
                compressed_buffer_ptr += 2;
                decompressed_buffer_ptr += ml;
            }
            else {
                // literal
                *compressed_buffer_ptr++ = *decompressed_buffer_ptr++;
            }
        }
    }

    return compressed_buffer_ptr - compressed_buffer;
}

Acknowledgements

• https://encode.su/threads/3555-Reverse-Engineering-Asobo-Custom-LZ-Variant-With-Multiple-Known-Past-Versions
• https://encode.su/threads/3625-Derive-LZSS-Compression-Algorithm-From-Decompression-Algorithm-(Asobo-LZ-Variant)
• https://encode.su/threads/3526-Asobo-s-Ratatouille-DPC-Data-Compression
• https://encode.su/threads/3147-Reverse-Engineering-Custom-LZ-Variant