# Compression algorithm working with bitstream

I'm trying to reverse decompression algorithm for one of old games. After some reversing I found that it reads bit stream, not byte by byte. It looks like this:

``````std::vector<uint32_t> TABLE_1 = {0x10, 0x11, 0x12, 0, 8, 7, 9, 6, 0x0A, 5, 0x0B, 4, 0x0C, 3, 0x0D, 2, 0x0E, 1, 0x0F};

uint32_t f1()
{
if (_stream_end < 5)
{
read_to_stream();
}

uint32_t v1 = read_from_stream(0x1F, 5) + 0x101;
std::cout << "f1:: v1 = " << v1 << std::endl;

if (_stream_end < 5)
{
read_to_stream();
}

uint32_t v2 = read_from_stream(0x1F, 5) + 1;
std::cout << "f1:: v2 = " << v2 << std::endl;

if (_stream_end < 4)
{
read_to_stream();
}

uint32_t v3 = read_from_stream(0xF, 4) + 4;
std::cout << "f1:: v3 = " << v3 << std::endl;

if (v1 > 0x11E || v2 > 0x1E)
{
std::cout << "f1:: v1 or v2 is above limit" << std::endl;
return 1;
}

std::vector<uint32_t> v4(19, 0);

if (v3 != 0)
{
for (uint32_t i = 0; i < v3; i++)
{
if (_stream_end < 3)
{
read_to_stream();
}
v4[TABLE_1[i]] = read_from_stream(0x7, 3);
}

std::cout << "v4 = [ ";
for (auto &item : v4)
{
std::cout << item << " ";
}
std::cout << "]" << std::endl;
}

// rest of the code
}

uint32_t begin(uint32_t *value)
{
if (_stream_end == 0)
{
read_to_stream();
}

*value = read_from_stream(0x1, 1);

uint32_t result = read_from_stream(0x3, 2);

if (result == 2)
{
f1();
}

if (result == 1)
{
// execute subroutine
}

if (result == 0)
{
// execute subroutine
}

// rest of code
}

uint32_t read_from_stream(uint32_t mask, uint32_t count)
{

uint32_t result = _stream & mask;

_stream = _stream >> count;
_stream_end -= count;

return result;
}

void read_to_stream()
{
uint32_t byte = static_cast<uint32_t>(read_byte() & 0xFF);
_stream = _stream | (byte << _stream_end);
_stream_end += 8;
}

char read_byte()
{
if (_buffer_cursor == _buffer.size())
{
throw new std::runtime_error("read_byte");
}

return _buffer[_buffer_cursor++];
}
``````

Also I found that it uses two buffers: A (32768 bytes) and B (4096 bytes). First it fills in A buffer and after that uses it to fill in B buffer. From B buffer it copies data to output buffer so I guess it is uncompressed at this step. Maybe you could tell me what algorithms uses same kind of decompression.

Here are some other tables from that code.

``````byte_5E00E8     db 8 dup(0), 1, 0, 1, 0, 2, 0, 2, 0, 3, 0, 3, 0, 4, 0
db 4, 0, 5, 0, 5, 0, 6, 0, 6, 0, 7, 0, 7, 0, 8, 0, 8, 0
db 9, 0, 9, 0, 0Ah, 0, 0Ah, 0, 0Bh, 0, 0Bh, 0, 0Ch, 0
db 0Ch, 0, 0Dh, 0, 0Dh, 0

word_5E00AC     dw 1, 2, 3, 4, 5, 7, 9, 0Dh, 11h, 19h, 21h, 31h, 41h, 61h
dw 81h, 0C1h, 101h, 181h, 201h, 301h, 401h, 601h, 801h
dw 0C01h, 1001h, 1801h, 2001h, 3001h, 4001h, 6001h
``````

This two tables used together in one of functions (hard to reverse because it is a bit long and complicates). I may be wrong in mu suggestions because I'm not a reverse engineering specialist.

Here are two files: https://www.dropbox.com/s/4km2rjmfwi2dw1e/Archive.zip?dl=0

Update.

Guys, I checked one of previous developer's game (with source code published) and found that they used same library for compression (library link).

I think question does not make any sense now but let's keep it here for history.

• Have you considered that the game is using Huffman encoding with a fixed Huffman table? The tables you give provide too little detail. Deflate (used by gzip) has been around quite a while under a very liberal license and is one of the compression algos using Huffman encoding. – 0xC0000022L Jun 24 '18 at 20:33
• It would help if you post a link to at least one of the compressed files (and preferably more, if it is a custom scheme). – Jongware Jun 24 '18 at 20:48
• @usr2564301 OK. See link in my update. – John Tracid Jun 24 '18 at 22:03