Ich versuche einen funktionierenden aber noch zu komplex aussehenden/unverstandenenen Algorithmus zur Dekompression von Daten zu simplifizieren der Algorithmus stammt aus meinem Reverse Engineering Projekt zum DOS Spiel Alpha Waves und wird für den Game-Code und die Spieldaten wie Grafiken usw. verwendet Github: https://github.com/LowLevelMahn/alpha_waves_loader d.h. der Algorithmus ist ehemals DOS 16bit Binärcode den ich mit IDA Pro in Assembler-Code umgewandelt haben und dann ueber ein paar Umwege in C/C++ Code der Algorithmus ist vollständig und kann alle Daten die ich habe entpacken es gibt keine Fehler oder Probleme ich möchte den Algorithmus nur weiter vereinfachen und bräuchte ein paar Tips was das für ein Kompressions-Algorithmus sein können und wie ich die Iteration+Stack in eine Rekursive Lösung verwandeln könnte alle Namen von Variablen basieren auf der Position im Original Code und sind keine logischen/sinnvollen Namen also falls jemand Lust hat (es gibt so wenig Entwickler die sich für Reverse-Engineering begeistern können) darf hier gerne seinen Senf zu abgeben das self-contained Beispiel sollte mit jedem C++14 Compiler bauen und enthält einen einfach Unit-Test https://github.com/LowLevelMahn/alpha_waves_loader/blob/main/read_some_file_sub_4/example.cpp hier die Routine die mir noch Kopfschmerzen bereitete - sieht aus wie eine Rekursive (wegen dem Stack) RLE Kompression oder sowas
1 | void val_3_non_0( uint8_t*& uncompressed_, const tables_t& tables_, const uint8_t val_3_ ) |
2 | {
|
3 | struct stack_vals_t |
4 | {
|
5 | uint8_t val_0{}; |
6 | uint8_t val_1{}; |
7 | };
|
8 | |
9 | std::stack<stack_vals_t> stack; |
10 | |
11 | auto pushing = [&stack, &tables_]( const uint8_t val_7_ ) { |
12 | stack.push( { val_7_, tables_.table2[val_7_] } ); |
13 | return tables_.table1[val_7_]; |
14 | };
|
15 | |
16 | auto popping = [&stack]( uint8_t* val_7_, uint8_t* val_4_ ) { |
17 | if( stack.empty() ) |
18 | {
|
19 | return true; |
20 | }
|
21 | |
22 | const stack_vals_t stack_val = stack.top(); |
23 | stack.pop(); |
24 | *val_7_ = stack_val.val_0; |
25 | *val_4_ = stack_val.val_1; |
26 | |
27 | return false; |
28 | };
|
29 | |
30 | uint8_t val_7 = val_3_; |
31 | uint8_t val_4 = pushing( val_7 ); |
32 | |
33 | while( true ) |
34 | {
|
35 | const uint8_t val_5 = val_4; |
36 | const uint8_t val_6 = tables_.table3[val_5]; |
37 | |
38 | if( val_6 == 0 ) |
39 | {
|
40 | *uncompressed_++ = val_4; |
41 | if( popping( &val_7, &val_4 ) ) |
42 | {
|
43 | return; |
44 | }
|
45 | }
|
46 | else if( val_7 > val_6 ) |
47 | {
|
48 | val_7 = val_6; |
49 | val_4 = pushing( val_7 ); |
50 | }
|
51 | else
|
52 | {
|
53 | val_4 = val_7; |
54 | val_7 = val_6; |
55 | |
56 | assert( stack.size() >= 0 ); |
57 | while( true ) |
58 | {
|
59 | val_7 = tables_.table4[val_7]; |
60 | |
61 | if( val_7 == 0 ) |
62 | {
|
63 | *uncompressed_++ = val_5; |
64 | if( popping( &val_7, &val_4 ) ) |
65 | {
|
66 | return; |
67 | }
|
68 | break; |
69 | }
|
70 | else if( val_7 < val_4 ) |
71 | {
|
72 | val_4 = pushing( val_7 ); |
73 | break; |
74 | }
|
75 | |
76 | // another run
|
77 | }
|
78 | }
|
79 | }
|
80 | }
|
hier noch der Original-Code der Routine: https://github.com/LowLevelMahn/alpha_waves_loader/blob/db422a5475a1939427b6379e688d23844535b7a9/ae.asm#L970 oder meine C++/Assembler-Emulation davon - um die Semantik des Algorithmus stubide "fehlerfreier" nach C/C++ Übertragen zu können: https://github.com/LowLevelMahn/alpha_waves_loader/blob/456b2731b654c3a04c909b44c77a6ab4602e5c21/read_some_file_sub_4/original_port.cpp#L9 Der disassemblierte Assemblercode ist so korrigiert das er ein binärgleiche Datei wie der Original Loader erzeugt d.h. es ist ist 100% Sicher das dieser Code vollständig und korrekt disassembliert ist btw: zur Problematik mit Reverse Engineering, das Game ist offiziell Freeware und ich habe mit dem Original-Author und dem DOS-Portierer Kontakt gehabt, rechtlich alles OK - leider hatten beide keine Quelltext-Sicherung :/