'reversed DOS game uncompression code: is that maybe a known compression method (RLE,...) or self-invented?

its a file uncompression routine from the 1990 DOS game Alpha Waves game loader (https://www.mobygames.com/game/continuum)

enter image description here

based on my https://github.com/LowLevelMahn/alpha_waves_loader reverse engineering project

first i've reversed the loader with IDA to a binary equal assemble-able asm code: https://github.com/LowLevelMahn/alpha_waves_loader/blob/db422a5475a1939427b6379e688d23844535b7a9/ae.asm#L970

then i've translated the code to fake-assembler code (keeping the semantic but be able to use 32bit C/C++ code) https://github.com/LowLevelMahn/alpha_waves_loader/blob/db422a5475a1939427b6379e688d23844535b7a9/read_some_file_sub_4/original_port.cpp#L9

the last step was a small unit test comparing the original fake-assembler code against a more and more cleanuped version of the algorithm https://github.com/LowLevelMahn/alpha_waves_loader/blob/db422a5475a1939427b6379e688d23844535b7a9/read_some_file_sub_4/cleanup_port.cpp#L151

the reversed algorithm works with all compressed game data, got 100% coverage and a unit-test, the variable names are still a bit clumsy as i didn't understand the uncompresse algorithm fully

i've got a small (except the test data size) unit-test that got a nearly 100% coverage of the algorithm (execept the uncompress block case - that can be skipped here) compiles standalone - out-of the box with a C++14 compiler VS2017+, gcc, clang tested https://github.com/LowLevelMahn/alpha_waves_loader/blob/main/read_some_file_sub_4/example.cpp

online compile & debug-able at: https://onlinegdb.com/VjiONQjAu

can anyone tell me if that is some sort of standard (un)compression algorithm from the early times or something completely self-invented by the game creator? (its dramatically reduced compared to the original asm but still not super-trivial)

the code seems to be recursive - flattened by using a stack while uncompression

void val_3_non_0( uint8_t*& uncompressed_, const tables_t& tables_, const uint8_t val_3_ )
{
    struct stack_vals_t
    {
        uint8_t val_0{};
        uint8_t val_1{};
    };

    std::stack<stack_vals_t> stack;

    auto helper1 = [&stack, &tables_]( const uint8_t val_7_ ) {
        stack.push( { val_7_, tables_.table2[val_7_] } );
        return tables_.table1[val_7_];
    };

    auto helper2 = [&stack]( uint8_t* val_7_, uint8_t* val_4_ ) {
        if( stack.empty() )
        {
            return true;
        }

        const stack_vals_t stack_val = stack.top();
        stack.pop();
        *val_7_ = stack_val.val_0;
        *val_4_ = stack_val.val_1;

        return false;
    };

    uint8_t val_7 = val_3_;
    uint8_t val_4 = helper1( val_7 );

    while( true )
    {
        const uint8_t val_5 = val_4;
        const uint8_t val_6 = tables_.table3[val_5];

        if( val_6 == 0 )
        {
            *uncompressed_++ = val_4;
            if( helper2( &val_7, &val_4 ) )
            {
                return;
            }
        }
        else if( val_7 > val_6 )
        {
            val_7 = val_6;
            val_4 = helper1( val_7 );
        }
        else
        {
            val_4 = val_7;
            val_7 = val_6;

            assert( stack.size() >= 0 );
            while( true )
            {
                val_7 = tables_.table4[val_7];

                if( val_7 == 0 )
                {
                    *uncompressed_++ = val_5;
                    if( helper2( &val_7, &val_4 ) )
                    {
                        return;
                    }
                    break;
                }
                else if( val_7 < val_4 )
                {
                    val_4 = helper1( val_7 );
                    break;
                }

                // another run
            }
        }
    }
}


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source