Ponowne użycie znaków w skompilowanym pliku .exe

Question

Dawno, dawno temu, z ciekawości, próbowałem hex-edit pliku wykonywalnego gry "Dangerous Dave". Rozejrzałem się po pliku w poszukiwaniu znalezionych ciągów znaków i wprowadziłem kilka losowych zmian, aby sprawdzić, czy rzeczywiście zmieni on tekst wyświetlany w grze.

Byłem zaskoczony, aby zobaczyć wynik, który mam teraz odtworzone za pomocą hex-edytora i DOSBox:

Jak widać, edytując dwa znaki „RO” w ciągu „ROMERO” spowodowało w 4 znaki są zmieniane, z wynikiem staje się "ZUMEZU". Wygląda na to, że program ponownie używa dwóch znaków i drukuje je na początku i końcu tego ciągu.

Jaka jest tego przyczyna? Moim pierwszym przypuszczeniem byłaby próba zmniejszenia pliku wykonywalnego, ale kod, który ponownie użyłby znaków, prawdopodobnie wymagałby więcej miejsca niż te 2 bajty do zapisania. Czy to tylko sztuczka wykonana przez autora, czy tylko jakiś kompilator voodoo?

Answer 1

Trudno powiedzieć na pewno bez inżynierii odwrotnej, ale zgaduję, że wiele stałych danych w programie jest kompresowanych za pomocą algorytmu z LZ family. Te schematy kompresji działają zasadniczo w sposób, który obserwujesz: kodują powtarzające się podciągi jako odniesienia do tekstu, który został wcześniej zdekodowany.

Te algorytmy kompresji były prawdopodobnie używane dla więcej niż tylko jednego ciągu, a nie tylko dla tekstu; jest całkiem możliwe, że były również używane do kompresowania innych danych, takich jak grafika lub układ poziomów. Krótko mówiąc, prawdopodobnie zastosowano znaczne oszczędności dzięki zastosowaniu tego algorytmu!

Korzystanie z tych algorytmów kompresji jest powszechne w starszych grach jako sposób na zaoszczędzenie miejsca na dysku, ale nie było automatyczne - implementacja tego algorytmu prawdopodobnie byłaby czymś, co sam Romero dodał.