'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)
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 |
|---|

